A. K-интересные подотрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В древнем королевстве Бурляндия мудрый математик Вася открыл таинственное свойство некоторых массивов. Согласно древним свиткам, $$$k$$$-интересные массивы содержат ключ к поиску скрытых сокровищ по всему королевству.

Вася определяет массив $$$a$$$ длины $$$n$$$ как $$$k$$$-интересный, если существует такой индекс $$$i$$$ $$$(1 \leq i \lt n)$$$, что:

$$$$$$ (a_1 + a_2 + ... + a_i) \cdot a_{i+1} \cdot a_{i+2} \cdot ... \cdot a_{n} = k$$$$$$

Иными словами, сумма первых $$$i$$$ элементов, умноженная на произведение оставшихся элементов, равна $$$k$$$.

Король Артур, очарованный этими массивами, владеет картой, представленной в виде массива $$$а$$$ длины $$$n$$$. Он подозревает, что некоторые части этой карты могут привести к различным сокровищам, каждое из которых связано с определенным значением $$$k$$$.

Королевские советники подготовили $$$q$$$ запросов для анализа этой карты. Всего есть два типа запросов. Каждый запрос первого типа задаётся тремя числами $$$l$$$, $$$r$$$ и $$$k$$$. Ваша задача — проверить, правда ли, что подмассив массива $$$a$$$ с $$$l$$$-го по $$$r$$$-й элементы является $$$k$$$-интересным. Кроме того, советники иногда обновляют карту новой информацией. Эти обновления представлены как запросы второго типа. Каждый запрос второго типа задан двумя числами $$$i$$$ и $$$x$$$, которые обозначают, что теперь $$$i$$$-й элемент массива $$$a$$$ равен $$$x$$$.

Помогите королю Артуру найти сокровища до того, как их обнаружат другие королевства!

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

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

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

Каждая из следующих $$$q$$$ строк описывает запрос в одном из следующих форматов:

  • $$$1$$$ $$$l$$$ $$$r$$$ $$$k$$$ — нужно проверить, является ли подмассив $$$[l; r]$$$ массива $$$a$$$ $$$k$$$-интересным $$$(1 \leq l \lt r \leq n, 1 \leq k \leq 10^{18})$$$.
  • $$$2$$$ $$$i$$$ $$$x$$$ — нужно присвоить $$$a_i$$$ значение $$$x$$$ $$$(1 \leq i \leq n, 1 \leq x \leq 10^9)$$$.
Выходные данные

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
$$$1$$$$$$12$$$$$$n,q \leq 200$$$
$$$2$$$$$$9$$$$$$n \leq 200$$$, запросы только 1-го типа
$$$3$$$$$$14$$$$$$n, q \leq 3000$$$, запросы только 1-го типа
$$$4$$$$$$7$$$$$$n, q \leq 3000$$$1,3
$$$5$$$$$$15$$$В любой момент $$$a_i$$$ четно, запросы только 1-го типа
$$$6$$$$$$12$$$В любой момент $$$a_i$$$ четно5
$$$7$$$$$$20$$$Запросы только 1-го типа2,3,5
$$$8$$$$$$11$$$—1,2,3,4,5,6,7
Примеры
Входные данные
5 4
5 2 7 10 2
1 2 4 90
2 4 11
1 2 4 90
1 1 5 308
Выходные данные
YES
NO
YES
Входные данные
7 6
4 6 4 2 9 10 7
2 7 3
2 4 8
1 3 4 32
2 7 7
2 3 10
1 4 6 720
Выходные данные
YES
YES
Примечание

Разберем первый пример из условия. В первом запросе нас просят проверить, является ли подмассив $$$[2, 7, 10]$$$ $$$90$$$-интересным. Он является таковым, так как $$$(2 + 7)\cdot 10 = 90$$$.

После второго запроса массив выглядит следующим образом: $$$[5, 2, 7, 11, 2]$$$.

В третьем запросе нас просят проверить, является ли подмассив $$$[2, 7, 11]$$$ $$$90$$$-интересным. Он таковым не является, так как мы не можем выбрать такое $$$i$$$, чтобы произведение суммы первых $$$i$$$ элементов и остальных элементов было равно $$$90$$$.

В четвертом запросе нас просят проверить, является ли массив целиком $$$308$$$-интересным. Он является таковым, так как $$$(5 + 2 + 7) \cdot 11 \cdot 2 = 308$$$.