Description:
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 Format:
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 Format:
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).
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.