G. Аня и таинственная строка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ане подарили строку $$$s$$$ длины $$$n$$$, привезённую из Рима. Строка $$$s$$$ состоит из маленьких латинских букв и на первый взгляд не вызывает подозрений. К строке была приложена инструкция.

Начало инструкции.

Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, строки «anna», «aboba», «level» являются палиндромами, а строки «gorilla», «banan», «off» — нет.

Подстрокой $$$[l \ldots r]$$$ строки $$$s$$$ называется строка $$$s_l s_{l+1} \ldots s_{r-1} s_r$$$. Например, подстрокой $$$[4 \ldots 6]$$$ строки «generation» является строка «era».

Строка называется красивой, если она не содержит подстроки длины хотя бы два, являющейся палиндромом. Например, строки «fox», «abcdef» и «yioy» красивые, а строки «xyxx», «yikjkitrb» — нет.

Когда к символу $$$s_i$$$ прибавляют целое положительное число $$$x$$$, он $$$x$$$ раз заменяется на следующий в алфавите, при этом «z» заменяется на «a».

Когда к подстроке $$$[l, r]$$$ строки $$$s$$$ прибавляют целое положительное число $$$x$$$, она превращается в строку $$$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$$$. Например, при прибавлении к подстроке $$$[2, 4]$$$ строки «abazaba» числа $$$6$$$, получится строка «ahgfaba».

Конец инструкции.

После прочтения инструкции Аня смирилась с тем, что ей предстоит ответить на $$$m$$$ запросов. Запросы бывают двух типов:

  1. Прибавить к подстроке $$$[l \ldots r]$$$ строки $$$s$$$ число $$$x$$$.
  2. Сказать, является ли подстрока $$$[l \ldots r]$$$ строки $$$s$$$ красивой.
Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

В первой строке даны целые числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длина строки $$$s$$$ и количество запросов.

Во второй строке дана строка $$$s$$$ длины $$$n$$$, состоящая из маленьких букв латинского алфавита.

Следующие $$$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$$$.

Выходные данные

Для каждого запроса второго типа выведите «YES», если подстрока $$$[l \ldots r]$$$ строки $$$s$$$ является красивой, в противном случае выведите «NO».

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
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
Выходные данные
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 является красивой.