D. Единицы и двойки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$ в $$$1$$$-нумерации, каждый элемент которого равен $$$1$$$ или $$$2$$$.

Обработайте $$$q$$$ запросов следующих двух типов:

  • «1 s»: проверить, существует ли подотрезок$$$^{\dagger}$$$ массива $$$a$$$, сумма которого равна $$$s$$$.
  • «2 i v»: заменить $$$a_i$$$ на $$$v$$$.

$$$^{\dagger}$$$ Массив $$$b$$$ является подотрезком массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов из начала и нескольких (возможно, нуля или всех) элементов из конца. В частности, массив является подотрезком самого себя.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ равно $$$1$$$ или $$$2$$$) — элементы массива $$$a$$$.

Каждая из следующих $$$q$$$ строк каждого набора входных данных содержит некоторое количество целых чисел. Первое целое число $$$\mathrm{op}$$$ равно либо $$$1$$$, либо $$$2$$$.

  • Если $$$\mathrm{op}$$$ равно $$$1$$$, то за ним следует одно целое число $$$s$$$ ($$$1 \leq s \leq 2n$$$).
  • Если $$$\mathrm{op}$$$ равно $$$2$$$, то за ним следуют два целых числа $$$i$$$ и $$$v$$$ ($$$1 \leq i \leq n$$$, $$$v$$$ равно $$$1$$$ или $$$2$$$).

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

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

Для каждого запроса с $$$\mathrm{op}=1$$$ выведите в отдельной строке «YES», если существует подотрезок $$$a$$$, сумма которого равна $$$s$$$, в противном выведите «NO».

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

Пример
Входные данные
2
5 5
2 1 2 1 2
1 5
1 6
1 7
2 4 2
1 7
3 2
2 2 2
1 6
1 5
Выходные данные
YES
YES
NO
YES
YES
NO
Примечание

Рассмотрим первый набор входных данных:

  • Ответом на первый запрос будет «YES», потому что $$$a_1+a_2+a_3=2+1+2=5$$$.
  • Ответ на второй запрос — «YES», потому что $$$a_1+a_2+a_3+a_4=2+1+2+1=6$$$.
  • Ответом на третий запрос будет «NO», так как нельзя найти ни одного подотрезка $$$a$$$, сумма которого равна $$$7$$$.
  • После четвертого запроса массив $$$a$$$ становится равным $$$[2,1,2,2,2]$$$.
  • Ответом на пятый запрос будет «YES», так как $$$a_2+a_3+a_4+a_5=1+2+2+2=7$$$.