AmShZ Wins a Bet

题意翻译

蓝有一个括号串 $S$，其中括号串定义为仅由 `(` 和 `)` 组成的字符串。 现在她进行了任意次如下操作： - 将 $S$ 分为三个可以为空的连续子串 $A,B,C$，接着将 $S$ 变为一个新串 $A(B)C$（即在 $B$ 前加上左括号，在 $B$ 后加上右括号）。 接着，她给出了经过她任意次操作后的括号串 $S$，她希望你能还原出原串 $S'$，使得 $S'$ 的字典序最小。 对于两个字符串 $a$ 和 $b$，若 $a$ 字典序比 $b$ 小，那么满足如下条件： - $a$ 为 $b$ 的前缀，且 $a\neq b$； - 令 $i$ 为最小的数使得 $a_i\neq b_i$，那么 $a_i$ 为左括号。 本题数据满足：$1 \leq |S| \leq 3\times10^5$。

题目描述

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. 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 \ne 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 $ .

输入输出格式

输入格式

The only line of input contains a single string $ S $ — the string after the operations $ (1\le |S|\le 3 \cdot 10^5) $ . It is guaranteed that the first character of $ S $ is ')'.

输出格式

Print the lexicographically smallest possible initial string before operations.

输入输出样例

输入样例 #1

)(()(())))

输出样例 #1

)((())))

说明

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

题意翻译

蓝有一个括号串 $S$，其中括号串定义为仅由 `(` 和 `)` 组成的字符串。 现在她进行了任意次如下操作： - 将 $S$ 分为三个可以为空的连续子串 $A,B,C$，接着将 $S$ 变为一个新串 $A(B)C$（即在 $B$ 前加上左括号，在 $B$ 后加上右括号）。 接着，她给出了经过她任意次操作后的括号串 $S$，她希望你能还原出原串 $S'$，使得 $S'$ 的字典序最小。 对于两个字符串 $a$ 和 $b$，若 $a$ 字典序比 $b$ 小，那么满足如下条件： - $a$ 为 $b$ 的前缀，且 $a\neq b$； - 令 $i$ 为最小的数使得 $a_i\neq b_i$，那么 $a_i$ 为左括号。 本题数据满足：$1 \leq |S| \leq 3\times10^5$。