We define a valid bracket sequence as a string that is either:
- The empty string;
- A string
Bis a valid bracket sequence.
LR, the concatenation of two strings
Rwhich 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:
- , 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.
The input contains a string of lowercase letters on the first line.
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
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 .
'('is considered lexicographically smaller than character
Sample Input 1
Sample Output 1
Another valid bracket sequence is
this is not the smallest lexicographic
Sample Input 2
Sample Output 2
There is no valid bracket sequence that matches the given string.