13190번 - Match 다국어

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 B be a valid bracket sequence of length N. We define B_i to be the i-th character of sequence B. For two indices i and j, 1 ≤ i < j ≤ N, we say that B_i and B_j are matching brackets if:

• B_i = '(' and B_j = ')';
• i = j-1, or the subsequence C = B_i+1B_i+2 … B_j-1 is a valid bracket sequence.

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

• B has the same length as S;
• for any pair of indices i and j, i < j, if Bi and Bj are matching brackets, then S_i = S_j.

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.

• 2 ≤ N ≤ 100 000
• We say that a bracket sequence A is lexicographically smaller than a bracket sequence B if there is an index i, 1 ≤ i ≤ N, such that A_j = B_j for each j < i, and A_i < B_i.
• Character '(' is considered lexicographically smaller than character ')'.

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.