Задано два взаємно прості додатні цілі числа $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.