## CEOI '16 P4 - Match

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

We define a valid bracket sequence as a string that is either:

• The empty string;
• A string (B), where B is a valid bracket sequence.
• LR, the concatenation of two strings L and R which are both valid bracket sequences.

Let be a valid bracket sequence of length . We define to be the -th character of sequence . For two indices and , , we say that and are matching brackets if:

• ( and );
• , or the subsequence is a valid bracket sequence.

Let be a string of lowercase English letters. We define to be the -th character of string . We say that a valid bracket sequence matches if:

• has the same length as ;
• for any pair of indices and , if and are matching brackets, then .

For a given string consisting of lowercase letters, find the lexicographically smallest valid bracket sequence that matches , or print -1 if no such bracket sequence exists.

#### Input

The input contains a string of lowercase letters on the first line.

#### Output

In the output you should write either a string with characters that represents the lexicographically smallest bracket sequence that matches the input string, or -1 if no such bracket sequence exists.

#### Notes and constraints

• For test cases worth points .
• For test cases worth another points .
• We say that a bracket sequence is lexicographically smaller than a bracket sequence if there is an index , such that for each , and .
• Character ( is considered lexicographically smaller than character ).

#### Sample Input 1

abbaaa

#### Sample Output 1

(()())

#### Note for Sample Input 1

Another valid bracket sequence is (())(), but this is not the smallest lexicographic solution.

#### Sample Input 2

abab

#### Sample Output 2

-1

#### Note for Sample Input 2

There is no valid bracket sequence that matches the given string.