CF1610G AmShZ Wins a Bet

在 2020 年欧洲杯之前，AmShZ 和 Safar 打赌谁会成为冠军，AmShZ 赌意大利，Safar 赌法国。 当然，AmShZ 赢了。因此，Safar 给了他一个括号序列 $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 \times 10^5$）。 保证 $S$ 的第一个字符是 ')'。

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

在第一个样例中，可以将 ")((())))" 变为 ")(()(())))"，方法是将其切分为 ")("、空串和 "(())))"。可以证明这是字典序最小的初始字符串。 由 ChatGPT 4.1 翻译