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

Дано целое число $$$m$$$ ($$$2\leq m\leq 5\cdot 10^5$$$) и массив $$$a$$$, состоящий из неотрицательных целых чисел, меньших $$$m$$$.

Ответьте на запросы следующего вида:

  • $$$1$$$ $$$i$$$ $$$x$$$: присвоить $$$a_i := x$$$
  • $$$2$$$ $$$k$$$: за одно действие вы можете выбрать элемент $$$a_i$$$ и присвоить $$$a_i := (a_i + k) \pmod m$$$$$$^{\text{∗}}$$$  — определите, существует ли некоторая последовательность (возможно, из нуля) операций, чтобы сделать $$$a$$$ неубывающим$$$^{\text{†}}$$$.

Обратите внимание, что запросы типа $$$2$$$ независимы, то есть фактически эти операции не выполняются. Запросы типа $$$1$$$ являются постоянными.

$$$^{\text{∗}}$$$$$$a\pmod m$$$ определяется как уникальное целое число $$$b$$$, такое что $$$0\leq b \lt m$$$ и $$$a-b$$$ является целым кратным $$$m$$$.

$$$^{\text{†}}$$$Массив $$$a$$$ размера $$$n$$$ называется неубывающим, если и только если $$$a_i\leq a_{i+1}$$$ для всех $$$1\leq i \lt n$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$a_1,a_2,\dots,a_n$$$ ($$$0\leq a_i \lt m$$$).

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

  • $$$1$$$ $$$i$$$ $$$x$$$ ($$$1\leq i\leq n$$$, $$$0\leq x \lt m$$$)
  • $$$2$$$ $$$k$$$ ($$$1\leq k \lt m$$$)

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

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

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

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

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

В первом примере массив изначально выглядит так:

4522410

Применив операцию дважды к $$$a_1$$$, дважды к $$$a_2$$$, один раз к $$$a_5$$$, дважды к $$$a_6$$$ и один раз к $$$a_7$$$, массив становится:

0122234
который находится в неубывающем порядке.

После второго запроса массив становится:

4525410
и можно показать, что невозможно отсортировать его с помощью операций вида $$$a_i := (a_i+4)\pmod 6$$$, и также невозможно отсортировать его с помощью операций вида $$$a_i := (a_i+3)\pmod 6$$$.