Gefnar eru tvær ósamþátta jákvæðar heiltölur $p$ og $q$. Það eru $pq$ mismunandi tegundir af spilum, númeraðar $0, 1, \ldots, pq - 1$.

Það eru tvær gerðir af stöðluðum spilapökkum:

• Staðlaðir spilapakkar af gerð 1: það eru $p$ tegundir, númeraðar með $u$ ($0 \le u < p$). Pakkinn með númerið $u$ inniheldur eitt eintak af hverju spili sem hefur númer sem uppfyllir $x \equiv u \pmod{p}$, þannig að hver pakki inniheldur nákvæmlega $q$ spil.
• Staðlaðir spilapakkar af gerð 2: það eru $q$ tegundir, númeraðar með $v$ ($0 \le v < q$). Pakkinn með númerið $v$ inniheldur eitt eintak af hverju spili sem hefur númer sem uppfyllir $x \equiv v \pmod{q}$, þannig að hver pakki inniheldur nákvæmlega $p$ spil.

Nú liggja $n$ spil í röð á borðinu, þar sem númer $i$-ta spilsins er $a_i$. Þú þarft að framkvæma $Q$ aðgerðir af eftirfarandi tveimur gerðum:

• 1 i x: breyttu númeri $i$-ta spilsins í $x$;
• 2 l r: ákvarðaðu hvort hægt sé að skipta öllum spilunum á bilinu $[l, r]$ nákvæmlega upp í nokkra staðlaða spilapakka.

Athugasemd: Þegar spilunum er pakkað upp á nýtt verður hvert spil á bilinu að tilheyra nákvæmlega einum pakka, og nota má hverja tegund af stöðluðum spilapakka hversu oft sem er.

Inntak

Fyrsta línan inniheldur fjórar heiltölur $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$).

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), sem tákna upphafsnúmer hvers spils.

Næstu $Q$ línur lýsa hver um sig aðgerð á forminu 1 i x eða 2 l r:

• Fyrir hverja aðgerð af fyrri gerðinni er tryggt að $1 \le i \le n$ og $0 \le x < pq$.
• Fyrir hverja aðgerð af seinni gerðinni er tryggt að $1 \le l \le r \le n$.

Úttak

Fyrir hverja aðgerð af seinni gerðinni, ef hægt er að skipta tilgreindu spilunum nákvæmlega upp í nokkra staðlaða spilapakka, prentaðu YES; annars skaltu prenta NO.

Dæmi

Inntak 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

Úttak 1

YES
NO
NO
YES

Athugasemd

Þegar $p = 2, q = 3$:

• Það eru tveir staðlaðir spilapakkar af gerð 1: $\{0, 2, 4\}$ og $\{1, 3, 5\}$.
• Það eru þrír staðlaðir spilapakkar af gerð 2: $\{0, 3\}$, $\{1, 4\}$ og $\{2, 5\}$.

Fyrir fyrstu fyrirspurnina er fjölmengi spilanna á bilinu $\{0, 0, 2, 3, 4\}$. Hægt er að skipta því í $\{0, 2, 4\} + \{0, 3\}$, svo svarið er YES.

Fyrir síðustu fyrirspurnina er fjölmengi spilanna á bilinu $\{1, 4\}$. Það myndar nákvæmlega einn staðlaðan spilapakka af gerð 2, svo svarið er YES.