We define a valid bracket sequence as a string that is either:
 The empty string;
 A string
(B)
, whereB
is a valid bracket sequence. LR
, the concatenation of two stringsL
andR
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.
Comments