Transpose

AtCoder

IDabc350_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

((A)y)x

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.

Input #2

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

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.

Input #3

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

Output #3

The final outcome may be an empty string.

Input #4

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

Output #4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve

API Response (JSON)

{
  "problem": {
    "name": "Transpose",
    "description": {
      "content": "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 followi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc350_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S = S_1 S_2 S_3 \\dots S_{|S|}$ consisting of uppercase and lowercase English letters, `(`, and `)`.  \nThe parentheses in the string $S$ are properly matched.\nRepeat the followi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments