Anya收到了从罗马带来的长度为$$$n$$$的字符串$$$s$$$。字符串 $$$s$$$ 由小写拉丁字母组成,乍一看不会引起任何怀疑。字符串上附加了一条指令。
指令开始。
回文是从左到右和从右到左读相同的字符串。例如,字符串“anna”、“aboba”、“level”是回文,而字符串“gorilla”、“banan”、“off”则不是。
字符串 $$$s$$$ 的子字符串 $$$[l \ldots r]$$$ 是字符串 $$$s_l s_{l+1} \ldots s_{r-1} s_r$$$。例如,字符串“ Generation”的子字符串$$$[4 \ldots 6]$$$是字符串“era”。
如果一个字符串不包含长度至少为 2 的回文子串,则该字符串被称为漂亮字符串。例如,字符串“fox”、“abcdef”和“yioy”很漂亮,而字符串“xyxx”、“yikjkitrb”则不然。
当整数 $$$x$$$ 添加到字符 $$$s_i$$$ 时,它会被字母表中的下一个字符替换 $$$x$$$ 次,其中“z”被“a”替换。
当整数 $$$x$$$ 被添加到字符串 $$$s$$$ 的子串 $$$[l, r]$$$ 时,它变成字符串 $$$s_1 s_2 \ldots s_{l-1} (s_l + x) (s_{l+1} + x) \ldots (s_{r-1} + x) (s_r + x) s_{r+1} \ldots s_n$$$。例如,当字符串“abazaba”的子字符串$$$[2, 4]$$$与数字$$$6$$$相加时,得到的字符串为“ahgfaba”。
指令结束。
读完说明后,安雅接受了她必须回答 $$$m$$$ 询问的事实。查询可以有两种类型:
1. 将数字 $$$x$$$ 添加到字符串 $$$s$$$ 的子字符串 $$$[l \ldots r]$$$ 中。
2、判断字符串$$$s$$$的子串$$$[l \ldots r]$$$是否漂亮。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) - 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 字符串 $$$s$$$ 的长度和查询次数。
每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,由小写拉丁字母组成。
接下来的 $$$m$$$ 行包含查询:
- $$$1$$$ $$$l$$$ $$$r$$$ $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^9$$$) - 第一种类型查询的描述;
- $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) - 第二类型查询的描述。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于第二类的每个查询,如果字符串$$$s$$$的子串$$$[l \ldots r]$$$漂亮,则输出“YES”,否则输出“NO”。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
5 12 8 tedubcyyxopz 2 2 5 1 4 8 2 2 1 7 1 3 5 40 1 9 11 3 1 10 10 9 2 4 10 2 10 12 10 4 ubnxwwgzjt 2 4 10 2 10 10 1 6 10 8 2 7 7 11 3 hntcxfxyhtu 1 4 6 1 2 4 10 1 4 10 21 13 2 yxhlmzfhqctir 1 5 9 3 1 8 13 15 2 3 bp 1 1 2 15 1 1 2 18 1 2 2 1000000000
输出 #1
YES NO NO YES NO YES YES YES
注意
在第一个测试的第一个测试用例中,发生以下情况:
- tedubcyyxopz:字符串 edub 很漂亮;
- tedubcyyxopz $$$\to$$$ tedwdeaaxopz;
- tedwdeaaxopz:字符串 tedwdea 并不美观,因为它包含回文 edwde;
- tedwdeaaxopz $$$\to$$$ terkreaaxopz;
- terkreaaxopz $$$\to$$$ terkreaaarsz;
- terkreaaarsz $$$\to$$$ terkreaaaasz;
- terkreaaaasz:字符串 kreaaaa 并不美观,因为它包含回文 aaaa;
- terkreaaaasz:字符串 asz 很漂亮。