問題文

左右対称な括弧列 を、以下のいずれかの条件を満たす 空でない 文字列と定義します。

• ()
• ある左右対称な括弧列 $s$ が存在し、(, $s$, ) をこの順に連結した文字列

また、(, ) のいずれかからなる文字列 $s$ に対して、スコア を以下のように定義します。

• 以下の操作を繰り返すことができる回数。
• $s$ の 連続 部分列であって左右対称な括弧列であるようなもののうち、最長のものを $1$ つ選び、削除する。
• なお、部分列を取り除く順番に拠らずこの回数が一意に定まることは証明可能である。

(, ) のいずれかからなる長さ $N$ の文字列 $S$ があります。

$S$ に対して $Q$ 個のクエリが与えられるので、順に処理してください。クエリは $2$ 種類あり、入力形式とクエリの内容は以下の通りです。

• 1 i: $S$ の $i$ 文字目を、(, ) のうち現在とは異なる文字に変更する。
• 2 l r: $S$ の $l$ 文字目から $r$ 文字目を取り出した部分文字列のスコアを出力する。

入力

$N$ $Q$
$S$
${\mathrm{query}}_1$
${\mathrm{query}}_2$
$⋮$
${\mathrm{query}}_Q$

• $N$ は $1\le N\le 2\times {10}^5$ を満たす整数
• $Q$ は $1\le Q\le 2\times {10}^5$ を満たす整数
• $S$ は (, ) のいずれかからなる長さ $N$ の文字列
• 1 i の形式のクエリについて、$i$ は $1\le i\le N$ を満たす整数
• 2 l r の形式のクエリについて、$l,r$ は $1\le l\le r\le N$ を満たす整数
• 2 l r の形式のクエリが $1$ 回以上登場する

出力

2 l r の形式のクエリそれぞれについて、$1$ 行に答えを出力してください。

出力クエリ $1$ つごとに改行してください。

サンプル

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

1
2