F - Transpose Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

英大小文字と ( 、 ) からなる文字列 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 中の ( と ) を順序を保って抜き出した時、それが正しい括弧列となることを指す。

制約

  • 1 \le |S| \le 5 \times 10^5
  • S は英大小文字と ( 、 ) からなる
  • S 中の括弧は対応が取れている

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

((A)y)x

出力例 1

YAx

S= ((A)y)x に対して操作を行います。

  • l=2,r=4 を選択します。このとき削除される文字列は (A) で、代わりに a が挿入されます。
    • この操作の結果、 S= (ay)x となります。
  • l=1,r=4 を選択します。このとき削除される文字列は (ay) で、代わりに YA が挿入されます。
    • この操作の結果、 S= YAx となります。

括弧を除去した結果、文字列は YAx となったので、これを出力してください。

入力例 2

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

出力例 2

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 となったので、これを出力してください。

入力例 3

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

出力例 3



操作結果が空文字列になる場合もあります。













入力例 4
dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve












出力例 4
dFGsdccCrFNNnplCtQPOKjsiIwwEysAve







Score: 550 points







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