Du får två relativt prima positiva heltal $p$ och $q$. Det finns $pq$ olika typer av kort, numrerade $0, 1, \ldots, pq - 1$.

Det finns två typer av standardkortpaket:

• Typ 1-standardkortpaket: det finns $p$ sorter, numrerade med $u$ ($0 \le u < p$). Paketet med nummer $u$ innehåller ett exemplar av varje kort vars nummer uppfyller $x \equiv u \pmod{p}$, så varje paket innehåller exakt $q$ kort.
• Typ 2-standardkortpaket: det finns $q$ sorter, numrerade med $v$ ($0 \le v < q$). Paketet med nummer $v$ innehåller ett exemplar av varje kort vars nummer uppfyller $x \equiv v \pmod{q}$, så varje paket innehåller exakt $p$ kort.

Det ligger nu $n$ kort utlagda på bordet, där numret på det $i$-te kortet är $a_i$. Du ska behandla $Q$ operationer av följande två typer:

• 1 i x: ersätt numret på det $i$-te kortet med $x$;
• 2 l r: avgör om alla kort i intervallet $[l, r]$ kan delas upp exakt i ett antal standardkortpaket.

Notera: När korten packas om måste varje kort i intervallet tillhöra exakt ett paket, och varje sort av standardkortpaket får användas valfritt antal gånger.

Indata

Den första raden innehåller fyra heltal $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 andra raden innehåller $n$ heltal $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), som anger det ursprungliga numret på varje kort.

De följande $Q$ raderna beskriver var och en en operation på formen 1 i x eller 2 l r:

• För varje operation av den första typen garanteras att $1 \le i \le n$ och $0 \le x < pq$.
• För varje operation av den andra typen garanteras att $1 \le l \le r \le n$.

Utdata

För varje operation av den andra typen, om de angivna korten kan delas upp exakt i ett antal standardkortpaket, skriv ut YES; annars, skriv ut NO.

Exempel

Indata 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

Notering

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

• Det finns två Typ 1-standardkortpaket: $\{0, 2, 4\}$ och $\{1, 3, 5\}$.
• Det finns tre Typ 2-standardkortpaket: $\{0, 3\}$, $\{1, 4\}$ och $\{2, 5\}$.

För den första frågan är multimängden av kort i intervallet $\{0, 0, 2, 3, 4\}$. Den kan delas upp i $\{0, 2, 4\} + \{0, 3\}$, så svaret är YES.

För den sista frågan är multimängden av kort i intervallet $\{1, 4\}$. Den utgör exakt ett Typ 2-standardkortpaket, så svaret är YES.