Du får oppgitt to relativt primiske positive heltall $p$ og $q$. Det finnes $pq$ forskjellige typer kort, nummerert $0, 1, \ldots, pq - 1$.

Det finnes to typer standard kortpakker:

• Type 1-standardkortpakker: det finnes $p$ slag, nummerert med $u$ ($0 \le u < p$). Pakken med nummer $u$ inneholder ett eksemplar av hvert kort hvis nummer oppfyller $x \equiv u \pmod{p}$, slik at hver pakke inneholder nøyaktig $q$ kort.
• Type 2-standardkortpakker: det finnes $q$ slag, nummerert med $v$ ($0 \le v < q$). Pakken med nummer $v$ inneholder ett eksemplar av hvert kort hvis nummer oppfyller $x \equiv v \pmod{q}$, slik at hver pakke inneholder nøyaktig $p$ kort.

Det ligger nå $n$ kortstilt opp på bordet, der nummeret på det $i$-te kortet er $a_i$. Du må behandle $Q$ operasjoner av følgende to typer:

• 1 i x: erstatt nummeret på det $i$-te kortet med $x$;
• 2 l r: avgjør om alle kortene i intervallet $[l, r]$ kan deles opp nøyaktig i flere standard kortpakker.

Merk: Når kortene pakkes om, må hvert kort i intervallet tilhøre nøyaktig én pakke, og hvert slag av standard kortpakke kan brukes et hvilket som helst antall ganger.

Inndata

Den første linjen inneholder fire heltall $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$).

Den andre linjen inneholder $n$ heltall $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), som angir startnummeret til hvert kort.

De neste $Q$ linjene beskriver hver en operasjon på formen 1 i x eller 2 l r:

• For hver operasjon av den første typen er det garantert at $1 \le i \le n$ og $0 \le x < pq$.
• For hver operasjon av den andre typen er det garantert at $1 \le l \le r \le n$.

Utdata

For hver operasjon av den andre typen, hvis de angitte kortene kan deles opp nøyaktig i flere standard kortpakker, skriv ut YES; ellers skriv ut NO.

Eksempler

Inndata 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

Utdata 1

YES
NO
NO
YES

Merk

Når $p = 2, q = 3$:

• Det finnes to Type 1-standardkortpakker: $\{0, 2, 4\}$ og $\{1, 3, 5\}$.
• Det finnes tre Type 2-standardkortpakker: $\{0, 3\}$, $\{1, 4\}$ og $\{2, 5\}$.

For den første spørringen er multimengden av kort i intervallet $\{0, 0, 2, 3, 4\}$. Den kan deles opp i $\{0, 2, 4\} + \{0, 3\}$, så svaret er YES.

For den siste spørringen er multimengden av kort i intervallet $\{1, 4\}$. Den utgjør nøyaktig én Type 2-standardkortpakke, så svaret er YES.