Gegeben sind zwei teilerfremde positive ganze Zahlen $p$ und $q$. Es gibt $pq$ verschiedene Kartentypen, die mit $0, 1, \ldots, pq - 1$ nummeriert sind.
Es gibt zwei Typen von Standard-Kartenpaketen:
- Typ-1-Standard-Kartenpakete: Es gibt $p$ Sorten, nummeriert mit $u$ ($0 \le u < p$). Das Paket mit der Nummer $u$ enthält jeweils ein Exemplar jeder Karte, deren Nummer $x \equiv u \pmod{p}$ erfüllt, sodass jedes Paket genau $q$ Karten enthält.
- Typ-2-Standard-Kartenpakete: Es gibt $q$ Sorten, nummeriert mit $v$ ($0 \le v < q$). Das Paket mit der Nummer $v$ enthält jeweils ein Exemplar jeder Karte, deren Nummer $x \equiv v \pmod{q}$ erfüllt, sodass jedes Paket genau $p$ Karten enthält.
Nun liegen $n$ Karten auf dem Tisch, wobei die Nummer der $i$-ten Karte $a_i$ ist. Sie müssen $Q$ Operationen der folgenden zwei Typen verarbeiten:
1 i x: Ersetze die Nummer der $i$-ten Karte durch $x$;2 l r: Bestimme, ob alle Karten im Intervall $[l, r]$ exakt in mehrere Standard-Kartenpakete aufgeteilt werden können.
Hinweis: Beim Neuverpacken der Karten muss jede Karte im Intervall zu genau einem Paket gehören, und jede Sorte von Standard-Kartenpaketen darf beliebig oft verwendet werden.
Eingabe
Die erste Zeile enthält vier ganze Zahlen $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$).
Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), welche die anfängliche Nummer jeder Karte angeben.
Die nächsten $Q$ Zeilen beschreiben jeweils eine Operation in der Form 1 i x oder 2 l r:
- Für jede Operation des ersten Typs ist garantiert, dass $1 \le i \le n$ und $0 \le x < pq$ gilt.
- Für jede Operation des zweiten Typs ist garantiert, dass $1 \le l \le r \le n$ gilt.
Ausgabe
Geben Sie für jede Operation des zweiten Typs YES aus, falls die angegebenen Karten exakt in mehrere Standard-Kartenpakete aufgeteilt werden können; andernfalls geben Sie NO aus.
Beispiele
Eingabe 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
Ausgabe 1
YES NO NO YES
Hinweis
Wenn $p = 2, q = 3$ ist:
- Es gibt zwei Typ-1-Standard-Kartenpakete: $\{0, 2, 4\}$ und $\{1, 3, 5\}$.
- Es gibt drei Typ-2-Standard-Kartenpakete: $\{0, 3\}$, $\{1, 4\}$ und $\{2, 5\}$.
Für die erste Anfrage ist die Multimenge der Karten im Intervall $\{0, 0, 2, 3, 4\}$. Sie kann in $\{0, 2, 4\} + \{0, 3\}$ aufgeteilt werden, also lautet die Antwort YES.
Für die letzte Anfrage ist die Multimenge der Karten im Intervall $\{1, 4\}$. Sie bildet genau ein Typ-2-Standard-Kartenpaket, also lautet die Antwort YES.