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 𝑆S. Note that a bracket sequence is a string made of ‘(‘ and ‘)’ characters.

AmShZ can perform the following operation any number of times:

  • First, he cuts his string 𝑆S into three (possibly empty) contiguous substrings 𝐴,𝐵A,B and 𝐶C. Then, he glues them back by using a ‘(‘ and a ‘)’ characters, resulting in a new string 𝑆S = 𝐴A + “(” + 𝐵B + “)” + 𝐶C.For example, if 𝑆S = “))((” and AmShZ cuts it into 𝐴A = “”, 𝐵B = “))”, and 𝐶C = “((“, He will obtain 𝑆S = “()))((” 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.

AmShZ Wins a Bet solution codeforces

A string 𝑎a is lexicographically smaller than a string 𝑏b if and only if one of the following holds:

  • 𝑎a is a prefix of 𝑏b, but 𝑎𝑏a≠b;
  • in the first position where 𝑎a and 𝑏b differ, the string 𝑎a has a letter that appears earlier in the alphabet than the corresponding letter in 𝑏b.
Input

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

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

Output

Print the lexicographically smallest possible initial string before operations.

Example
input

Copy AmShZ Wins a Bet solution codeforces

)(()(())))
output

Copy
)((())))
Note

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

Your email address will not be published. Required fields are marked *