配点 : $500$ 点

問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

• 空文字列
• ある正しい括弧列 $A$ が存在して、(, $A$, ) をこの順に連結した文字列
• ある空でない正しい括弧列 $A$, $B$ が存在して、$A$, $B$ をこの順に連結した文字列

( と ) のみからなる長さ $N$ の文字列 $S$ があります。

$Q$ 個のクエリ $\text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q$ が与えられるので、順番に処理してください。クエリには $2$ 種類があり、入力形式とクエリの内容は以下の通りです。

• 1 l r : $S$ の $l$ 文字目と $r$ 文字目を入れ替える。
• 2 l r : $S$ の $l$ 文字目から $r$ 文字目までの連続部分文字列が正しい括弧列であるか判定する。

制約

• $1 \leq N,Q \leq 2 \times 10^5$
• $S$ は ( と ) のみからなる長さ $N$ の文字列
• $1 \leq l < r \leq N$
• $N,Q,l,r$ はいずれも整数
• 各クエリは 1 l r、2 l r のいずれかの形式で与えられる。
• 2 l r の形式のクエリは $1$ つ以上与えられる。

入力

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

$N$ $Q$

$S$

$\text{Query}_1$

$\text{Query}_2$

$\vdots$

$\text{Query}_Q$

出力

2 l r の形式の各クエリに対して、連続部分文字列が正しい括弧列である場合 Yes、そうでない場合 No と出力し、改行せよ。

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

Yes
No
No

$1$ つ目のクエリにおいて、(()) は正しい括弧列です。

$2$ つ目のクエリにおいて、(( は正しい括弧列ではありません。

$3$ つ目のクエリにおいて、)( は正しい括弧列ではありません。

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

Yes
No

$1$ つ目のクエリにおいて、(()) は正しい括弧列です。

$2$ つ目のクエリによって、$S$ は )()(( となります。

$3$ つ目のクエリにおいて、)()( は正しい括弧列ではありません。

8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

Yes
No
No