题目描述

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

• 空文字列
• ある正しい括弧列 $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$ 文字目までの連続部分文字列が正しい括弧列であるか判定する。

输入格式

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

$N$ $Q$ $S$ $\text{Query}_1$ $\text{Query}_2$ $\vdots$ $\text{Query}_Q$

输出格式

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

题目大意

给出一个括号串，$Q$ 次以下两种操作：

• 输入 $1\ l\ r$，代表交换第 $l$ 和第 $r$ 个位置上的字符

• 输入 $2\ l\ r$，判断区间 $[l,r]$ 子串是否是合法括号序列

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

Yes
No
No

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

Yes
No

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

提示

制約

• $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$ つ以上与えられる。

Sample Explanation 1

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

Sample Explanation 2

$1$ つ目のクエリにおいて、(()) は**正しい括弧列**です。 $2$ つ目のクエリによって、$S$ は )()(( となります。 $3$ つ目のクエリにおいて、)()( は**正しい括弧列**ではありません。