回文查询

题目描述

给定一个长度为 $N$,由小写英文字母组成的字符串 $S$。

请按顺序处理下面给出的 $Q$ 个查询。

查询有以下两种类型:

1 x c :将 $S$ 的第 $x$ 个字符改成小写英文字母 $c$。

2 L R :如果由 $S$ 的第 $L$ 到第 $R$ 个字符组成的子串是回文,则输出 Yes;否则输出 No。

输入格式

输入按以下格式从标准输入给出。这里,$\text{query}_i$ 表示要处理的第 $i$ 个查询。

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

每个查询按以下两种格式之一给出:

$1$ $x$ $c$

或

$2$ $L$ $R$

输出格式

按照题目要求,用换行分隔输出各查询的答案。

样例

7 8
abcbacb
2 1 5
2 4 7
2 2 2
1 5 c
2 1 5
2 4 7
1 4 c
2 3 6

Yes
No
Yes
No
Yes
Yes

初始时 $S =$ abcbacb。

对于第一个查询,由 $S$ 的第 $1$ 到第 $5$ 个字符组成的字符串是 abcba,它是回文,因此输出 Yes。

对于第二个查询,由 $S$ 的第 $4$ 到第 $7$ 个字符组成的字符串是 bacb,它不是回文,因此输出 No。

对于第三个查询,由 $S$ 的第 $2$ 到第 $2$ 个字符组成的字符串是 b,它是回文,因此输出 Yes。

对于第四个查询,将 $S$ 的第 $5$ 个字符改为 c。此时 $S$ 变为 abcbccb。

对于第五个查询,由 $S$ 的第 $1$ 到第 $5$ 个字符组成的字符串是 abcbc,它不是回文,因此输出 No。

对于第六个查询,由 $S$ 的第 $4$ 到第 $7$ 个字符组成的字符串是 bccb,它是回文,因此输出 Yes。

对于第七个查询,将 $S$ 的第 $4$ 个字符改为 c。此时 $S$ 变为 abccccb。

对于第八个查询,由 $S$ 的第 $3$ 到第 $6$ 个字符组成的字符串是 cccc,它是回文,因此输出 Yes。

数据范围

• $1 \le N \le 10^6$
• $1 \le Q \le 10^5$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串
• $1 \le x \le N$
• $c$ 是小写英文字母
• $1 \le L \le R \le N$
• $N, Q, x, L, R$ 均为整数