Annettuna on kaksi keskenään jaotonta positiivista kokonaislukua $p$ ja $q$. On olemassa $pq$ erilaista korttityyppiä, jotka on numeroitu $0, 1, \ldots, pq - 1$.

On olemassa kahdenlaisia vakiokorttipaketteja:

• Tyypin 1 vakiokorttipaketit: niitä on $p$ erilaista, numeroitu luvulla $u$ ($0 \le u < p$). Paketti numero $u$ sisältää yhden kappaleen jokaista korttia, jonka numero toteuttaa ehdon $x \equiv u \pmod{p}$, joten jokainen paketti sisältää täsmälleen $q$ korttia.
• Tyypin 2 vakiokorttipaketit: niitä on $q$ erilaista, numeroitu luvulla $v$ ($0 \le v < q$). Paketti numero $v$ sisältää yhden kappaleen jokaista korttia, jonka numero toteuttaa ehdon $x \equiv v \pmod{q}$, joten jokainen paketti sisältää täsmälleen $p$ korttia.

Pöydälle on nyt asetettu $n$ korttia, missä $i$-nnen kortin numero on $a_i$. Sinun tulee käsitellä $Q$ operaatiota, jotka ovat seuraavaa kahta tyyppiä:

• 1 i x: korvaa $i$-nnen kortin numero luvulla $x$;
• 2 l r: selvitä, voidaanko kaikki välillä $[l, r]$ olevat kortit jakaa tasan useiksi vakiokorttipaketeiksi.

Huomautus: Kortteja uudelleenpakattaessa jokaisen välillä olevan kortin täytyy kuulua täsmälleen yhteen pakettiin, ja kutakin vakiokorttipakettityyppiä saa käyttää mielivaltaisen monta kertaa.

Syöte

Ensimmäinen rivi sisältää neljä kokonaislukua $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$).

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), jotka ilmoittavat kunkin kortin alkunumeron.

Seuraavat $Q$ riviä kuvaavat kukin yhden operaation muodossa 1 i x tai 2 l r:

• Jokaiselle ensimmäisen tyypin operaatiolle on taattu, että $1 \le i \le n$ ja $0 \le x < pq$.
• Jokaiselle toisen tyypin operaatiolle on taattu, että $1 \le l \le r \le n$.

Tuloste

Jokaiselle toisen tyypin operaatiolle, jos määritetyt kortit voidaan jakaa tasan useiksi vakiokorttipaketeiksi, tulosta YES; muussa tapauksessa tulosta NO.

Esimerkit

Syöte 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

Tuloste 1

YES
NO
NO
YES

Huomautus

Kun $p = 2, q = 3$:

• Tyypin 1 vakiokorttipaketteja on kaksi: $\{0, 2, 4\}$ ja $\{1, 3, 5\}$.
• Tyypin 2 vakiokorttipaketteja on kolme: $\{0, 3\}$, $\{1, 4\}$ ja $\{2, 5\}$.

Ensimmäisessä kyselyssä välillä olevien korttien monijoukko on $\{0, 0, 2, 3, 4\}$. Se voidaan jakaa osiin $\{0, 2, 4\} + \{0, 3\}$, joten vastaus on YES.

Viimeisessä kyselyssä välillä olevien korttien monijoukko on $\{1, 4\}$. Se muodostaa täsmälleen yhden tyypin 2 vakiokorttipaketin, joten vastaus on YES.