Dane są dwie względnie pierwsze dodatnie liczby całkowite $p$ oraz $q$. Istnieje $pq$ różnych typów kart, ponumerowanych $0, 1, \ldots, pq - 1$.

Istnieją dwa rodzaje standardowych paczek kart:

• Standardowe paczki kart typu 1: jest ich $p$ odmian, ponumerowanych przez $u$ ($0 \le u < p$). Paczka o numerze $u$ zawiera po jednym egzemplarzu każdej karty, której numer spełnia $x \equiv u \pmod{p}$, więc każda paczka zawiera dokładnie $q$ kart.
• Standardowe paczki kart typu 2: jest ich $q$ odmian, ponumerowanych przez $v$ ($0 \le v < q$). Paczka o numerze $v$ zawiera po jednym egzemplarzu każdej karty, której numer spełnia $x \equiv v \pmod{q}$, więc każda paczka zawiera dokładnie $p$ kart.

Obecnie na stole ułożonych jest $n$ kart, gdzie numer $i$-tej karty to $a_i$. Musisz przetworzyć $Q$ operacji następujących dwóch rodzajów:

• 1 i x: zamień numer $i$-tej karty na $x$;
• 2 l r: rozstrzygnij, czy wszystkie karty z przedziału $[l, r]$ można dokładnie podzielić na pewną liczbę standardowych paczek kart.

Uwaga: Podczas przepakowywania kart każda karta z przedziału musi należeć do dokładnie jednej paczki, a każda odmiana standardowej paczki kart może zostać użyta dowolną liczbę razy.

Wejście

Pierwszy wiersz zawiera cztery liczby całkowite $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$).

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), oznaczających początkowy numer każdej karty.

Kolejne $Q$ wierszy opisuje po jednej operacji w postaci 1 i x lub 2 l r:

• Dla każdej operacji pierwszego rodzaju gwarantowane jest, że $1 \le i \le n$ oraz $0 \le x < pq$.
• Dla każdej operacji drugiego rodzaju gwarantowane jest, że $1 \le l \le r \le n$.

Wyjście

Dla każdej operacji drugiego rodzaju, jeśli wskazane karty można dokładnie podzielić na pewną liczbę standardowych paczek kart, wypisz YES; w przeciwnym razie wypisz NO.

Przykład

Wejście 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

Wyjście 1

YES
NO
NO
YES

Uwagi

Gdy $p = 2, q = 3$:

• Istnieją dwie standardowe paczki kart typu 1: $\{0, 2, 4\}$ oraz $\{1, 3, 5\}$.
• Istnieją trzy standardowe paczki kart typu 2: $\{0, 3\}$, $\{1, 4\}$ oraz $\{2, 5\}$.

Dla pierwszego zapytania multizbiór kart w przedziale to $\{0, 0, 2, 3, 4\}$. Można go podzielić na $\{0, 2, 4\} + \{0, 3\}$, więc odpowiedzią jest YES.

Dla ostatniego zapytania multizbiór kart w przedziale to $\{1, 4\}$. Tworzy on dokładnie jedną standardową paczkę kart typu 2, więc odpowiedzią jest YES.