CF1610G.AmShZ Wins a Bet

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

在欧洲杯2020开赛前，AmShZ 和 Safar 就谁将夺冠下了赌注：AmShZ 押意大利，Safar 押法国。

当然，AmShZ 赢了。因此，Safar 给了他一个括号序列 $S$。注意，括号序列是由字符 '(' 和 ')' 构成的字符串。

AmShZ 可以执行以下操作任意多次：

• 首先，他将字符串 $S$ 切割为三个（可能为空的）连续子串 $A$、$B$ 和 $C$；然后，他在 $A$ 和 $C$ 之间插入一对括号，即用 '(' 和 ')' 将它们连接起来，从而得到新字符串 $S = A + \text{``(''} + B + \text{``)''} + C$。

  例如，若 $S = \text{"))(("}$，AmShZ 将其切分为 $A = \text{``''}$（空串）、$B = \text{"))"}$、$C = \text{"(("}$，则他将得到新字符串 $S = \text{")))(("}$。

在执行若干次（可能为零次）上述操作后，AmShZ 将所得字符串交给 Keshi，并请他还原出原始字符串。当然，Keshi 可能还原出多个合法的初始字符串。Keshi 感兴趣的是找出字典序最小的可能初始字符串。

你的任务是帮助 Keshi 实现这一目标。

字符串 $a$ 的字典序小于字符串 $b$，当且仅当满足下列条件之一：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀但 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字符在字母表中早于 $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 ')'.

输入仅有一行，包含一个字符串 $S$ —— 经过操作后的字符串（$1\le |S|\le 3 \cdot 10^5$）。

保证 $S$ 的第一个字符为 ')'。

Print the lexicographically smallest possible initial string before operations.

输出操作前字典序最小的可能初始字符串。

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

在第一个样例中，你可以将 ")((())))" 拆分为 ")("、空字符串和 "(())))"，从而将其变换为 ")(()(())))"。可以证明，这是字典序最小的可能初始字符串。