AmShZ Wins a Bet solution codeforces

AmShZ Wins a Bet solution codeforces

Right before the UEFA Euro 2020, AmShZ and Safar placed bets on who’d be the champion, AmShZ betting on Italy, and Safar betting on France.

Of course, AmShZ won. Hence, Safar gave him a bracket sequence SS. Note that a bracket sequence is a string made of ‘(‘ and ‘)’ characters.

AmShZ can perform the following operation any number of times: AmShZ Wins a Bet solution codeforces

  • First, he cuts his string SS into three (possibly empty) contiguous substrings A,BA,B and CC. Then, he glues them back by using a ‘(‘ and a ‘)’ characters, resulting in a new string SS = AA + “(” + BB + “)” + CC.For example, if SS = “))((” and AmShZ cuts it into AA = “”, BB = “))”, and CC = “((“, He will obtain SS = “()))((” as a new string.

After performing some (possibly none) operations, AmShZ gives his string to Keshi and asks him to find the initial string. Of course, Keshi might be able to come up with more than one possible initial string. Keshi is interested in finding the lexicographically smallest possible initial string.

Your task is to help Keshi in achieving his goal.

A string aa is lexicographically smaller than a string bb if and only if one of the following holds:

  • aa is a prefix of bb, but aba≠b;
  • in the first position where aa and bb differ, the string aa has a letter that appears earlier in the alphabet than the corresponding letter in bb.
Input AmShZ Wins a Bet solution codeforces

The only line of input contains a single string SS — the string after the operations (1|S|3105)(1≤|S|≤3⋅105).

It is guaranteed that the first character of SS is ‘)’.

Output

Print the lexicographically smallest possible initial string before operations.

Example

input AmShZ Wins a Bet solution codeforces

Copy
)(()(())))

output

Copy
)((())))
Note AmShZ Wins a Bet solution codeforces

In the first sample, you can transform “)((())))” into “)(()(())))” by splitting it into “)(“, empty string, and “(())))”. It can be shown that this is the lexicographically smallest possible initial string

Leave a Comment