Даны два взаимно простых положительных целых числа $p$ и $q$. Существует $pq$ различных типов карт, пронумерованных $0, 1, \ldots, pq - 1$.

Существует два типа стандартных наборов карт:

• Стандартные наборы карт типа 1: всего их $p$ видов, занумерованных числом $u$ ($0 \le u < p$). Набор с номером $u$ содержит по одной копии каждой карты, номер которой удовлетворяет условию $x \equiv u \pmod{p}$, поэтому каждый набор содержит ровно $q$ карт.
• Стандартные наборы карт типа 2: всего их $q$ видов, занумерованных числом $v$ ($0 \le v < q$). Набор с номером $v$ содержит по одной копии каждой карты, номер которой удовлетворяет условию $x \equiv v \pmod{q}$, поэтому каждый набор содержит ровно $p$ карт.

Сейчас на столе выложены в ряд $n$ карт, где номер $i$-й карты равен $a_i$. Вам необходимо обработать $Q$ операций следующих двух типов:

• 1 i x: заменить номер $i$-й карты на $x$;
• 2 l r: определить, можно ли все карты на отрезке $[l, r]$ без остатка разбить на несколько стандартных наборов карт.

Примечание: При переупаковке карт каждая карта на отрезке должна принадлежать ровно одному набору, а каждый вид стандартного набора карт можно использовать произвольное число раз.

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

Первая строка содержит четыре целых числа $n, p, q, Q$ ($1 \le n, p, q, Q \le 3 \times 10^5$, $2 \le p + q \le 3 \times 10^5$, $\gcd(p, q) = 1$).

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), обозначающих начальный номер каждой карты.

Следующие $Q$ строк описывают по одной операции в формате 1 i x или 2 l r:

• Для каждой операции первого типа гарантируется, что $1 \le i \le n$ и $0 \le x < pq$.
• Для каждой операции второго типа гарантируется, что $1 \le l \le r \le n$.

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

Для каждой операции второго типа, если указанные карты можно без остатка разбить на несколько стандартных наборов карт, выведите YES; в противном случае выведите NO.

Примеры

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

8 2 3 5
0 0 2 3 4 1 4 2
2 1 5
2 6 8
1 8 5
2 6 8
2 6 7

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

YES
NO
NO
YES

Примечание

При $p = 2, q = 3$:

• Существует два стандартных набора карт типа 1: $\{0, 2, 4\}$ и $\{1, 3, 5\}$.
• Существует три стандартных набора карт типа 2: $\{0, 3\}$, $\{1, 4\}$ и $\{2, 5\}$.

Для первого запроса мультимножество карт на отрезке равно $\{0, 0, 2, 3, 4\}$. Его можно разбить на $\{0, 2, 4\} + \{0, 3\}$, поэтому ответ — YES.

Для последнего запроса мультимножество карт на отрезке равно $\{1, 4\}$. Оно образует ровно один стандартный набор карт типа 2, поэтому ответ — YES.