E. Маша и гирлянда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Маши есть новогодняя гирлянда, состоящая из $$$n$$$ лампочек. Каждая лампочка может быть либо выключена, либо включена. Состояние гирлянды задаётся бинарной строкой $$$s$$$ длины $$$n$$$, выключенные лампочки обозначены как '0', а включённые обозначены как '1'.

Маша считает гирлянду красивой, если состояния соседних лампочек строго чередуются. То есть не существует двух соседних лампочек, которые горят или не горят одновременно. Например, гирлянды '01010' и '1010' являются красивыми, а '0110' и '000' — нет.

Юра может применять к гирлянде следующую операцию: выбрать подотрезок гирлянды и сменить состояние всех лампочек на нём, то есть выключить все включённые и наоборот.

Маша предлагает ему $$$q$$$ раз сыграть в следующую игру: она выбирает отрезок с $$$l$$$-й по $$$r$$$-ю лампочку включительно, а Юра должен сделать этот отрезок красивым, использовав не более $$$k$$$ операций.

Однако Юра не уверен, что это возможно, так что он просит вас определить для каждой игры, получится ли у него сделать выбранный Машей отрезок красивым, сделав не более $$$k$$$ операций. Обратите внимание, что игры независимы, и фактические переключения лампочек не производятся (исходная гирлянда не изменяется).

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

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

В первой строке каждого набора задаются два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — длина гирлянды и количество игр.

Во второй строке задаётся бинарная строка $$$s$$$ длины $$$n$$$, состоящая только из символов '0' и '1'.

Следующие $$$q$$$ строк содержат по три целых числа $$$l$$$, $$$r$$$ и $$$k$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le k \le n$$$) — границы рассматриваемого отрезка гирлянды и максимально допустимое количество операций.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^5$$$.

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

Для каждой игры выведите «YES», если отрезок можно сделать красивым, переключив не более $$$k$$$ подотрезков, и «NO» в противном случае.

Пример
Входные данные
2
5 5
00110
1 5 1
1 5 2
2 4 1
1 2 0
3 4 0
4 2
1010
1 4 0
2 3 1
Выходные данные
YES
YES
YES
NO
NO
YES
YES