|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||1||1||1||100.000%|
We define a valid bracket sequence as a string that is either:
Let B be a valid bracket sequence of length N. We define Bi to be the i-th character of sequence B. For two indices i and j, 1 ≤ i < j ≤ N, we say that Bi and Bj are matching brackets if:
Let S be a string of lowercase English letters. We define Si to be the i-th character of string S. We say that a valid bracket sequence B matches S if:
For a given string S consisting of N lowercase letters, find the lexicographically smallest valid bracket sequence that matches S, or print -1 if no such bracket sequence exists.
The input contains a string S of N lowercase letters on the first line.
In the output you should write either a string B with N characters that represents the lexicographically smallest bracket sequence that matches the input string, or -1 if no such bracket sequence exists.
Another valid bracket sequence is (())(), but this is not the smallest lexicographic solution.
There is no valid bracket sequence that matches the given string.