CF1881G.Anya and the Mysterious String

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.

安雅收到了一个来自罗马、长度为 $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 的回文子串，则称其为优美的（beautiful）。例如，字符串 "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.$$

例如，将数字 $6$ 加到字符串 "abazaba" 的子串 $[2, 4]$ 上，所得字符串为 "ahgfaba"。

说明结束。

读完说明后，安雅意识到自己必须回答 $m$ 个查询。这些查询分为两类：

1. 将数字 $x$ 加到字符串 $s$ 的子串 $[l \ldots r]$ 上；
2. 判断字符串 $s$ 的子串 $[l \ldots r]$ 是否为优美的。

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$.

第一行包含一个整数 $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$。

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).

对于每个第二类查询，如果字符串 $s$ 的子串 $[l \ldots r]$ 是优美的，则输出 “YES”，否则输出 “NO”。

“YES” 和 “NO” 可以以任意大小写形式输出（例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答）。

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.

在第一组测试数据的第一个测试用例中，发生如下过程：

• tedubcyyxopz：子串 edub 是优美的；
• tedubcyyxopz $\to$ tedwdeaaxopz；
• tedwdeaaxopz：子串 tedwdea 不是优美的，因为它包含回文子串 edwde；
• tedwdeaaxopz $\to$ terkreaaxopz；
• terkreaaxopz $\to$ terkreaaarsz；
• terkreaaarsz $\to$ terkreaaaasz；
• terkreaaaasz：子串 kreaaaa 不是优美的，因为它包含回文子串 aaaa；
• terkreaaaasz：子串 asz 是优美的。