Score: $550$ points

问题陈述

给定一个字符串 $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$ 中的括号是正确匹配的。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a string $S = S_1 S_2 S_3 \dots S_{|S|}$ consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string $S$ are properly matched.

Repeat the following operation until no more operations can be performed:

• First, select one pair of integers $(l, r)$ that satisfies all of the following conditions:
  • $l < r$
  • $S_l =$ (
  • $S_r =$ )
  • Each of the characters $S_{l+1}, S_{l+2}, \dots, S_{r-1}$ is an uppercase or lowercase English letter.
• Let $T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}$.
  • Here, $\overline{x}$ denotes the string obtained by toggling the case of each character in $x$ (uppercase to lowercase and vice versa).
• Then, delete the $l$-th through $r$-th characters of $S$ and insert $T$ at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

What does it mean that the parentheses in $S$ are properly matched? First, a correct parenthesis sequence is defined as follows:

• A correct parenthesis sequence is a string that satisfies one of the following conditions:

• It is an empty string.

• There exists a correct parenthesis sequence $A$, and the string is formed by concatenating (, $A$, ) in this order.

• There exist non-empty correct parenthesis sequences $A$ and $B$, and the string is formed by concatenating $A$ and $B$ in this order.

The parentheses in $S$ are properly matched if and only if the (s and )s extracted from $S$ without changing the order form a correct parenthesis sequence.

Constraints

• $1 \le |S| \le 5 \times 10^5$
• $S$ consists of uppercase and lowercase English letters, (, and ).
• The parentheses in $S$ are properly matched.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print the final string.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for $S =$ ((A)y)x.

• Choose $l=2$ and $r=4$. The substring (A) is removed and replaced with a.
  • After this operation, $S =$ (ay)x.
• Choose $l=1$ and $r=4$. The substring (ay) is removed and replaced with YA.
  • After this operation, $S =$ YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

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

Sample Output 2

XYZNXYZ

Let us perform the operations for $S =$ ((XYZ)n(X(y)Z)).

• Choose $l=10$ and $r=12$. The substring (y) is removed and replaced with Y.
  • After this operation, $S =$ ((XYZ)n(XYZ)).
• Choose $l=2$ and $r=6$. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, $S =$ (zyxn(XYZ)).
• Choose $l=6$ and $r=10$. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, $S =$ (zyxnzyx).
• Choose $l=1$ and $r=9$. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
  • After this operation, $S =$ XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

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

Sample Output 3

The final outcome may be an empty string.

Sample Input 4

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

Sample Output 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve