問題文

高橋君は「カッコつけ」です。開きカッコ(と閉じカッコ)だけからなる文字列に、新しくカッコを挿入したり削除したりするのが大好きです。 また、各文字列には「カッコ悪さ」という値が定義されます。ある文字列 $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行で出力せよ。

---

入力例1

5
(()
D 1 0
( 3 0
Q 1 2
) 1 0
Q 2 4

出力例1

0
1

$1$ 回目の操作が終わったあとの状態は ()

$2$ 回目の操作が終わったあとの状態は ())

$3$ 回目の操作で質問されている範囲の文字列は ()

$4$ 回目の操作が終わったあとの状態は (())

$5$ 回目の操作で質問されている範囲の文字列は ())

---

入力例2

11
(()()(()
( 1 0
( 1 0
D 4 0
Q 2 6
) 5 0
D 8 0
Q 1 9
( 3 0
) 8 0
D 10 0
Q 5 10

出力例2

1
1
4

$1$ 回目の操作が終わったあとの状態は ((()()(()

$2$ 回目の操作が終わったあとの状態は (((()()(()

$3$ 回目の操作が終わったあとの状態は ((()()(()

$4$ 回目の操作で質問されている範囲の文字列は (()()

$5$ 回目の操作が終わったあとの状態は ((())()(()

$6$ 回目の操作が終わったあとの状態は ((())()()

$7$ 回目の操作で質問されている範囲の文字列は ((())()()

$8$ 回目の操作が終わったあとの状態は (((())()()

$9$ 回目の操作が終わったあとの状態は (((())())()

$10$ 回目の操作が終わったあとの状態は (((())()))

$11$ 回目の操作で質問されている範囲の文字列は ))()))

---