就在 2020 年欧洲杯之前,AmShZ 和 Safar 押注谁将成为冠军,AmShZ 押注意大利,Safar 押注法国。
当然,AmShZ 赢了。因此,萨法尔给了他一个括号序列$$$S$$$。请注意,括号序列是由“(”和“)”字符组成的字符串。
AmShZ 可以执行任意多次以下操作:
- 首先,他将字符串 $$$S$$$ 切成三个(可能为空)连续的子字符串 $$$A、B$$$ 和 $$$C$$$。然后,他使用 '(' 和 ')' 字符将它们粘回去,从而生成一个新字符串 $$$S$$$ = $$$A$$$ + "(" + $$$B$$$ + ")" + $$$C$$$。例如,如果 $$$S$$$ = "))((" 并且 AmShZ 将其切割为 $$$A$$$ = "", $$$B$$$ = "))",并且$$$C$$$ = "((", 他将得到 $$$S$$$ = "()))((" 作为一个新字符串。
执行一些(可能没有)操作后,AmShZ 将他的字符串交给 Keshi 并要求他找到初始字符串。当然,Keshi 或许能够想出不止一个可能的初始字符串。 Keshi 感兴趣的是找到字典顺序上最小的可能初始字符串。
你的任务是帮助Keshi实现他的目标。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。
输入
输入的唯一一行包含单个字符串 $$$S$$$ — 操作 $$$(1\le |S|\le 3 \cdot 10^5)$$$ 后的字符串。
保证$$$S$$$的第一个字符是')'。
输出
在操作之前打印字典顺序最小的可能初始字符串。
示例
输入 #1
)(()(())))
输出 #1
)((())))
注意
在第一个示例中,您可以将“)((())))”转换为“)(()(())))”,方法是将其拆分为“)(”、空字符串和“(())))”。可以证明这是按字典顺序最小的可能初始字符串