转置

题目描述

给定一个由大写英文字母、小写英文字母、( 和 ) 组成的字符串 $S = S_1 S_2 S_3 \dots S_{|S|}$。

字符串 $S$ 中的括号是正确匹配的。

重复以下操作,直到无法再进行操作:

首先,选择一对满足以下所有条件的整数 $(l, r)$:

• $l \lt 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$。

请参考样例输入输出来理解。

可以证明,通过上述操作一定可以移除字符串中所有的 ( 和 ),并且最终字符串与操作的方式和顺序无关。

求最终字符串。

「括号正确匹配」是什么意思?

首先,正确括号序列定义如下:

正确括号序列是满足以下条件之一的字符串:

• 空字符串。
• 存在一个正确括号序列 $A$,字符串按 (,$A$,) 的顺序连接而成。
• 存在非空的正确括号序列 $A$ 和 $B$,字符串由 $A$ 和 $B$ 连接而成。

当且仅当从 $S$ 中按顺序提取出的 ( 和 ) 构成一个正确括号序列时,称 $S$ 中的括号是正确匹配的。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出最终字符串。

样例

((A)y)x

YAx

对 $S =$ ((A)y)x 进行操作。

选择 $l=2$,$r=4$。子串 (A) 被删除并替换为 a。

此操作后,$S =$ (ay)x。

选择 $l=1$,$r=4$。子串 (ay) 被删除并替换为 YA。

此操作后,$S =$ YAx。

移除括号后,字符串变为 YAx,应输出它。

((XYZ)n(X(y)Z))

XYZNXYZ

对 $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,应输出它。

(((()))(()))(())

最终结果可能是空字符串。

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve

数据范围

• $1 \le |S| \le 5 \times 10^5$
• $S$ 由大写英文字母、小写英文字母、( 和 ) 组成。
• $S$ 中的括号是正确匹配的。