AT_code_festival_exhibition_b カッコつけ

[problemUrl]: https://atcoder.jp/contests/code-festival-2014-exhibition/tasks/code_festival_exhibition_b 高橋君は「カッコつけ」です。開きカッコ`(`と閉じカッコ`)`だけからなる文字列に、新しくカッコを挿入したり削除したりするのが大好きです。 また、各文字列には「カッコ悪さ」という値が定義されます。ある文字列 $ S $ を「完璧」にするために取り除くべき文字の個数の最小値が「カッコ悪さ」です。 カッコ付けの対応に矛盾がなかった場合その文字列は「完璧」であると言います。特に、0文字の文字列も「完璧」です。 例えば `()()(())`という文字列は「完璧」で、「カッコ悪さ」は $ 0 $ です。 `())`は最後のカッコを取り除くと「完璧」になります。よって「カッコ悪さ」は $ 1 $ です。 高橋君は文字列 $ S $ を友人からもらいました。今からこの文字列に開きカッコや閉じカッコを挿入したり、削除したりします。 高橋君はときどき、いまの文字列うちの一部分の「カッコ悪さ」が気になります。 あなたは、高橋君が「カッコ悪さ」を質問した時に、それを求めてください。

入力は以下の形式で標準入力から与えられる > $ Q $ $ S $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ : $ x_Q $ $ y_Q $ $ z_Q $ - $ 1 $ 行目には高橋君が行う操作(質問含む)の回数 $ Q\ (1\ ≦\ Q\ ≦\ 10^5) $ が与えられる。 - $ 2 $ 行目には高橋君がもらった文字列 $ S\ (1\ ≦\ |\ S\ |\ ≦\ 10^5) $ が与えられる。 - $ 3 $ 行目からの $ Q $ 行のうち $ i $ 行目には $ i $ 番目の操作の内容を表す文字 $ x_i $ と数値 $ y_i,\ z_i $ が空白区切りで与えられる。 - $ x_i $が`(`のとき、開きカッコを挿入する操作を表す。$ y_i $番目に開きカッコを挿入する操作である。このとき$ z_i $は常に$ 0 $である。 - $ x_i $が`)`のとき、閉じカッコを挿入する操作を表す。$ y_i $番目に閉じカッコを挿入する操作である。このとき$ z_i $は常に$ 0 $である。 - $ x_i $が`D`のとき、削除する操作を表す。$ y_i $番目の文字列を削除する操作である。このとき$ z_i $は常に$ 0 $である。 - $ x_i $が`Q`のとき、質問する操作を表す。$ y_i $番目から$ z_i $番目の間(端を含む)の文字列の「カッコ悪さ」を質問するということである。 - 存在しない位置の文字を削除したり、質問したり、存在しない位置に文字を挿入するような入力は無い。また、与えられる全ての位置は1-indexedである。

出力は複数行からなる。 高橋君が質問するたびにその答えを1行で出力せよ。

### Sample Explanation 1 $ 1 $ 回目の操作が終わったあとの状態は `()` $ 2 $ 回目の操作が終わったあとの状態は `())` $ 3 $ 回目の操作で質問されている範囲の文字列は `()` $ 4 $ 回目の操作が終わったあとの状態は `(())` $ 5 $ 回目の操作で質問されている範囲の文字列は `())` ### Sample Explanation 2 $ 1 $ 回目の操作が終わったあとの状態は `((()()(()` $ 2 $ 回目の操作が終わったあとの状態は `(((()()(()` $ 3 $ 回目の操作が終わったあとの状態は `((()()(()` $ 4 $ 回目の操作で質問されている範囲の文字列は `(()()` $ 5 $ 回目の操作が終わったあとの状態は `((())()(()` $ 6 $ 回目の操作が終わったあとの状態は `((())()()` $ 7 $ 回目の操作で質問されている範囲の文字列は `((())()()` $ 8 $ 回目の操作が終わったあとの状態は `(((())()()` $ 9 $ 回目の操作が終わったあとの状態は `(((())())()` $ 10 $ 回目の操作が終わったあとの状態は `(((())()))` $ 11 $ 回目の操作で質問されている範囲の文字列は `))()))`