AT_abc350_f [ABC350F] Transpose

[problemUrl]: https://atcoder.jp/contests/abc350/tasks/abc350_f 英大小文字と `(` 、 `)` からなる文字列 $ S=S_1\ S_2\ S_3\ \dots\ S_{|S|} $ が与えられます。 文字列 $ S $ 中の括弧は、対応が取れています。 次の操作を、操作ができなくなるまで繰り返します。 - まず、以下の条件を全て満たす整数組 $ (l,r) $ をひとつ選択する。 - $ l\

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

答えを出力せよ。

### 制約 - $ 1\ \le\ |S|\ \le\ 5\ \times\ 10^5 $ - $ S $ は英大小文字と `(` 、 `)` からなる - $ S $ 中の括弧は対応が取れている ### Sample Explanation 1 $ S= $ `((A)y)x` に対して操作を行います。 - $ l=2,r=4 $ を選択します。このとき削除される文字列は `(A)` で、代わりに `a` が挿入されます。 - この操作の結果、 $ S= $ `(ay)x` となります。 - $ l=1,r=4 $ を選択します。このとき削除される文字列は `(ay)` で、代わりに `YA` が挿入されます。 - この操作の結果、 $ S= $ `YAx` となります。 括弧を除去した結果、文字列は `YAx` となったので、これを出力してください。 ### Sample Explanation 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` となったので、これを出力してください。 ### Sample Explanation 3 操作結果が空文字列になる場合もあります。