AT_abc350_f [ABC350F] Transpose

给定一个由英文字母大小写和 `(`、`)` 组成的字符串 $S = S_1 S_2 S_3 \dots S_{|S|}$。 字符串 $S$ 中的括号是配对的。 重复进行如下操作，直到无法继续为止： - 首先，选择一组满足以下所有条件的整数对 $(l, r)$： - $l < r$ - $S_l = ($ - $S_r = )$ - $S_{l+1}, S_{l+2}, \dots, S_{r-1}$ 全部为英文字母（大写或小写） - 令 $T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}$。 - 其中，$\overline{x}$ 表示将字符串 $x$ 的大小写反转后的结果。 - 然后，将 $S$ 的第 $l$ 个字符到第 $r$ 个字符删除，并在该位置插入 $T$。 具体操作过程请参见输入输出样例。 通过上述操作，可以将所有的 `(` 和 `)` 都去除，并且最终得到的字符串与操作的方法和顺序无关，这一点可以得到证明。 请输出最终得到的字符串。 “$S$ 中的括号是配对的”是什么意思？首先，定义“正确的括号序列”如下： - 空字符串 - 存在某个正确的括号序列 $A$，将 `(`、$A$、`)` 按此顺序连接得到的字符串 - 存在某些非空的正确括号序列 $A, B$，将 $A, B$ 按此顺序连接得到的字符串 $S$ 中的括号是配对的，指的是将 $S$ 中的所有 `(` 和 `)` 按顺序取出后，它们组成的字符串是一个正确的括号序列。

输入以以下格式从标准输入读入。 > $S$

请输出答案。

### 限制条件 - $1 \leq |S| \leq 5 \times 10^5$ - $S$ 由英文字母大小写和 `(`、`)` 组成 - $S$ 中的括号是配对的 ### 样例解释 1 对于 $S=$ `((A)y)x`，操作如下： - 选择 $l=2, r=4$。此时被删除的字符串为 `(A)`，插入 `a`。 - 操作后，$S=$ `(ay)x`。 - 选择 $l=1, r=4$。此时被删除的字符串为 `(ay)`，插入 `YA`。 - 操作后，$S=$ `YAx`。 括号全部去除后，字符串为 `YAx`，请输出该字符串。 ### 样例解释 2 对于 $S=$ `((XYZ)n(X(y)Z))`，操作如下： - 选择 $l=10, r=12$。此时被删除的字符串为 `(y)`，插入 `Y`。 - 操作后，$S=$ `((XYZ)n(XYZ))`。 - 选择 $l=2, r=6$。此时被删除的字符串为 `(XYZ)`，插入 `zyx`。 - 操作后，$S=$ `(zyxn(XYZ))`。 - 选择 $l=6, r=10$。此时被删除的字符串为 `(XYZ)`，插入 `zyx`。 - 操作后，$S=$ `(zyxnzyx)`。 - 选择 $l=1, r=9$。此时被删除的字符串为 `(zyxnzyx)`，插入 `XYZNXYZ`。 - 操作后，$S=$ `XYZNXYZ`。 括号全部去除后，字符串为 `XYZNXYZ`，请输出该字符串。 ### 样例解释 3 操作结果也可能为空字符串。 由 ChatGPT 4.1 翻译