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. 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 into three (possibly empty) contiguous substrings and . Then, he glues them back by using a ‘(‘ and a ‘)’ characters, resulting in a new string = + “(” + + “)” + .For example, if = “))((” and AmShZ cuts it into = “”, = “))”, and = “((“, He will obtain = “()))((” 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 stringis lexicographically smaller than a string if and only if one of the following holds:
- is a prefix of , but ;
- in the first position where and differ, the string has a letter that appears earlier in the alphabet than the corresponding letter in .
The only line of input contains a single string— the string after the operations .
It is guaranteed that the first character ofis ‘)’.
Print the lexicographically smallest possible initial string before operations.
input 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