F.

时间限制： 1 秒
空间限制： 512 MB
输入输出： 标准输入 / 标准输出

题目描述

在澳大利亚，大家从各种角度看待事物，因此他们用一种不同寻常的方式定义“正确括号序列”。

一个括号序列被认为是正确的，当且仅当它可以由以下规则构造：

1. 空序列是正确括号序列；
2. 如果 $S$ 是正确括号序列，那么 )S(、(S)、[S]、]S[、{S}、}S{、<S>、>S< 也都是正确括号序列；
3. 如果 $S$ 和 $T$ 都是正确括号序列，那么 $S+T$ 也是正确括号序列，其中 $+$ 表示字符串拼接。

现在给定一个由括号字符组成的字符串 $s$，并有 $m$ 个操作，操作分为两类：

1. 修改位置 $a_i$ 上的括号；
2. 询问子串 $s[l_i..r_i]$ 是否是澳大利亚意义下的正确括号序列。

请处理所有操作。

输入格式

第一行包含一个整数 $n$，表示括号序列长度。

第二行包含长度为 $n$ 的字符串 $s$，字符串只包含字符 ()[]{}<>。

第三行包含一个整数 $m$，表示操作数量。

接下来 $m$ 行，每行先输入一个整数 $t_i$：

• 若 $t_i=1$，接下来输入整数 $a_i$ 和字符 $c_i$，表示把 $s_{a_i}$ 修改为 $c_i$。保证 $c_i$ 是 ()[]{}<> 中的一个字符；
• 若 $t_i=2$，接下来输入整数 $l_i,r_i$，表示询问子串 $s[l_i..r_i]$ 是否正确。

输出格式

对于每个 $t_i=2$ 的询问，若对应子串是正确括号序列，输出 Yes；否则输出 No。

数据范围

$1 \le n \le 200000$，$1 \le m \le 200000$，$1 \le a_i \le n$，$1 \le l_i \le r_i \le n$。

样例

样例 1

6
)()(()
7
2 1 6
1 4 )
2 2 5
1 3 [
1 4 ]
2 1 6
2 4 5

Yes
Yes
Yes
No

样例 2

10
>())(][<}{
6
2 1 10
1 3 (
2 1 10
2 2 5
1 2 )
2 1 10

Yes
No
No
Yes

样例解释

样例 1 中，第一次询问的子串 )()(() 可以分解为若干个澳大利亚正确括号序列的拼接，因此答案为 Yes。之后经过修改，后续询问同理。最后一次询问子串 ]( 不正确，因此答案为 No。

样例 2 中，第一次询问对应的字符串可以按上述规则构造，因此答案为 Yes；经过修改后，部分子串不再正确，答案如输出所示。

子任务