310754: CF1881G. Anya and the Mysterious String

G. Anya and the Mysterious Stringtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Anya received a string $s$ of length $n$ brought from Rome. The string $s$ consists of lowercase Latin letters and at first glance does not raise any suspicions. An instruction was attached to the string.

Start of the instruction.

A palindrome is a string that reads the same from left to right and right to left. For example, the strings "anna", "aboba", "level" are palindromes, while the strings "gorilla", "banan", "off" are not.

A substring $[l \ldots r]$ of string $s$ is a string $s_l s_{l+1} \ldots s_{r-1} s_r$. For example, the substring $[4 \ldots 6]$ of the string "generation" is the string "era".

A string is called beautiful if it does not contain a substring of length at least two that is a palindrome. For example, the strings "fox", "abcdef", and "yioy" are beautiful, while the strings "xyxx", "yikjkitrb" are not.

When an integer $x$ is added to the character $s_i$, it is replaced $x$ times with the next character in the alphabet, with "z" being replaced by "a".

When an integer $x$ is added to the substring $[l, r]$ of string $s$, it becomes the string $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$. For example, when the substring $[2, 4]$ of the string "abazaba" is added with the number $6$, the resulting string is "ahgfaba".

End of the instruction.

After reading the instruction, Anya resigned herself to the fact that she has to answer $m$ queries. The queries can be of two types:

1. Add the number $x$ to the substring $[l \ldots r]$ of string $s$.
2. Determine whether the substring $[l \ldots r]$ of string $s$ is beautiful.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) - the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) - the length of the string $s$ and the number of queries.

The second line of each test case contains the string $s$ of length $n$, consisting of lowercase Latin letters.

The next $m$ lines contain the queries:

• $1$ $l$ $r$ $x$ ($1 \le l \le r \le n$, $1 \le x \le 10^9$) - description of a query of the first type;
• $2$ $l$ $r$ ($1 \le l \le r \le n$) - description of a query of the second type.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.

Output

For each query of the second type, output "YES" if the substring $[l \ldots r]$ of string $s$ is beautiful, otherwise output "NO".

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers).

ExampleInput

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

Output

YES
NO
NO
YES
NO
YES
YES
YES

Note

In the first test case of the first test, the following happens:

• tedubcyyxopz: the string edub is beautiful;
• tedubcyyxopz $\to$ tedwdeaaxopz;
• tedwdeaaxopz: the string tedwdea is not beautiful as it contains the palindrome edwde;
• tedwdeaaxopz $\to$ terkreaaxopz;
• terkreaaxopz $\to$ terkreaaarsz;
• terkreaaarsz $\to$ terkreaaaasz;
• terkreaaaasz: the string kreaaaa is not beautiful as it contains the palindrome aaaa;
• terkreaaaasz: the string asz is beautiful.

**题目大意：**

阿尼亚收到了一条来自罗马的字符串`s`，该字符串由小写拉丁字母组成，看起来并无异常。字符串附带了一份指令。

- 回文串：一个从左到右和从右到左读取都相同的字符串。
- 子串：字符串`s`中从第`l`个到第`r`个字符组成的字符串。
- 美丽字符串：不包含长度至少为2的回文子串的字符串。
- 字符串操作：将整数`x`加到`s`的子串`[l, r]`上，即将该子串中的每个字符在字母表中后移`x`位，`z`后面跟`a`。

阿尼亚需要回答`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：`1 l r x`（$1 \le l \le r \le n$, $1 \le x \le 10^9$），描述第一种类型的查询。
- 类型2：`2 l r`（$1 \le l \le r \le n$），描述第二种类型的查询。
- 保证所有测试用例的$n$和$m$之和不超过$2 \cdot 10^5$。

**输出：**

- 对于每个第二种类型的查询，如果字符串`s`的子串`[l \ldots r]`是美丽字符串，则输出`"YES"`，否则输出`"NO"`。
- `YES`和`NO`的大小写不敏感。**题目大意：** 阿尼亚收到了一条来自罗马的字符串`s`，该字符串由小写拉丁字母组成，看起来并无异常。字符串附带了一份指令。 - 回文串：一个从左到右和从右到左读取都相同的字符串。 - 子串：字符串`s`中从第`l`个到第`r`个字符组成的字符串。 - 美丽字符串：不包含长度至少为2的回文子串的字符串。 - 字符串操作：将整数`x`加到`s`的子串`[l, r]`上，即将该子串中的每个字符在字母表中后移`x`位，`z`后面跟`a`。 阿尼亚需要回答`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：`1 l r x`（$1 \le l \le r \le n$, $1 \le x \le 10^9$），描述第一种类型的查询。 - 类型2：`2 l r`（$1 \le l \le r \le n$），描述第二种类型的查询。 - 保证所有测试用例的$n$和$m$之和不超过$2 \cdot 10^5$。 **输出：** - 对于每个第二种类型的查询，如果字符串`s`的子串`[l \ldots r]`是美丽字符串，则输出`"YES"`，否则输出`"NO"`。 - `YES`和`NO`的大小写不敏感。