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

У вас есть массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел, и вам нужно обработать $$$q$$$ запросов двух типов:

  • $$$1$$$ $$$i$$$ $$$x$$$: заменить $$$a_{i}$$$ на $$$x$$$;
  • $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$: проверить, кратно ли числу $$$k$$$ количество вхождений каждого положительного целого числа в подмассив $$$a_{l}, a_{l+1}, \ldots a_{r}$$$ (смотрите пример для лучшего понимания).
Входные данные

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$) — элементы $$$a$$$.

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

  • $$$1$$$ $$$i$$$ $$$x$$$, ($$$1 \le i \le n$$$ , $$$1 \le x \le 10^9$$$), или
  • $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$, ($$$1 \le l \le r \le n$$$ , $$$1 \le k \le n$$$).
Выходные данные

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

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

В первом запросе запрашиваемый подмассив равен $$$[1234, 2, 3, 3, 2, 1]$$$, и очевидно, что количество вхождений $$$1$$$ не делится на $$$k = 2$$$. Так что ответ «NO».

В третьем запросе запрашиваемый подмассив равен $$$[1, 2, 3, 3, 2, 1]$$$, и видно, что количество вхождений каждого целого числа в этом подмассиве делится на $$$k = 2$$$. Поэтому ответ «YES».

В шестом запросе запрошенный подмассив равен $$$[1, 2, 3, 3, 2, 1, 1, 2, 3]$$$, и видно, что количество вхождений каждого целого числа в этом подмассиве кратно $$$k = 3$$$. Так что ответ «YES».