問題文

( と ) からなる長さ $N$ の文字列 $S$ が与えられます。 $Q$ 個のクエリが与えられます。クエリは次の $2$ 種類のいずれかです。与えられた順番に処理してください。

• 1 x t : 文字列 $S$ の $x$ 番目の文字を、$t=1$ ならば ( に、$t=2$ ならば ) に変更する。
• 2 l r : 文字列 $S$ の $l$ 番目から $r$ 番目までを抜き出した部分文字列を $T$ とする。文字列 $T$ に対して、以下の操作を行えなくなるまで繰り返したとき、削除することのできる文字数の最大値を出力しなさい。
  • $T$ の文字のうち、$a < b$ かつ $T_a =$ (、 $T_b =$ ) となるようなインデックス $a, b$ を選び、その $2$ 文字を削除する。残った文字列は元の順序を保ったまま連結される。
    (ここで、$T_a$, $T_b$ はそれぞれ、文字列 $T$ の $a$, $b$ 番目の文字を表します)

なお、すべてのテストケースでクエリ 2 l r は $1$ つ以上存在する事が保証されます。

制約

• $1 \le N, Q \le 2 \times 10^5$
• $S$ は ( と ) からなる長さ $N$ の文字列
• クエリ1について、$1 \le x \le N$
• クエリ1について、$t \in \{1, 2\}$
• クエリ2について、$1 \le l \le r \le N$
• $N, Q, x, t, l, r$ はすべて整数

入力

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

$N$ $Q$
$S$
$query_1$
$query_2$
$\vdots$
$query_Q$

各クエリ $query_i$ は以下のいずれかの形式です。

1 x t

2 l r

出力

タイプ $2$ のクエリの数を $k$ としたとき、$k$ 行出力してください。
$i$ 行目には、$i$ 番目のタイプ $2$ のクエリに対する答え（削除された文字の最大総数）を出力してください。
最後に改行してください。

サンプル

5 3
()(()
2 1 5
1 3 2
2 2 5

4
2

4 2
)(()
2 1 4
2 2 3

2
0

6 4
((()))
2 1 6
1 1 2
2 1 6
2 2 5

6
4
4