Ti vengono dati due interi positivi coprimi $p$ e $q$. Ci sono $pq$ tipi diversi di carte, numerati $0, 1, \ldots, pq - 1$.
Ci sono due tipi di pacchetti di carte standard:
- Pacchetti di carte standard di Tipo 1: ce ne sono di $p$ varietà, numerate da $u$ ($0 \le u < p$). Il pacchetto numerato $u$ contiene una copia di ogni carta il cui numero soddisfa $x \equiv u \pmod{p}$, quindi ogni pacchetto contiene esattamente $q$ carte.
- Pacchetti di carte standard di Tipo 2: ce ne sono di $q$ varietà, numerate da $v$ ($0 \le v < q$). Il pacchetto numerato $v$ contiene una copia di ogni carta il cui numero soddisfa $x \equiv v \pmod{q}$, quindi ogni pacchetto contiene esattamente $p$ carte.
Ora ci sono $n$ carte disposte sul tavolo, dove il numero della $i$-esima carta è $a_i$. Devi elaborare $Q$ operazioni dei seguenti due tipi:
1 i x: sostituisci il numero della $i$-esima carta con $x$;2 l r: determina se tutte le carte nell'intervallo $[l, r]$ possono essere partizionate esattamente in diversi pacchetti di carte standard.
Nota: Quando si riconfezionano le carte, ogni carta nell'intervallo deve appartenere a esattamente un pacchetto, e ciascuna varietà di pacchetto di carte standard può essere usata un numero qualsiasi di volte.
Input
La prima riga contiene quattro interi $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$).
La seconda riga contiene $n$ interi $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), che indicano il numero iniziale di ciascuna carta.
Le successive $Q$ righe descrivono ciascuna un'operazione nella forma 1 i x oppure 2 l r:
- Per ogni operazione del primo tipo, è garantito che $1 \le i \le n$ e $0 \le x < pq$.
- Per ogni operazione del secondo tipo, è garantito che $1 \le l \le r \le n$.
Output
Per ogni operazione del secondo tipo, se le carte specificate possono essere partizionate esattamente in diversi pacchetti di carte standard, stampa YES; altrimenti, stampa NO.
Esempi
Input 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
Output 1
YES NO NO YES
Nota
Quando $p = 2, q = 3$:
- Ci sono due pacchetti di carte standard di Tipo 1: $\{0, 2, 4\}$ e $\{1, 3, 5\}$.
- Ci sono tre pacchetti di carte standard di Tipo 2: $\{0, 3\}$, $\{1, 4\}$ e $\{2, 5\}$.
Per la prima query, il multinsieme di carte nell'intervallo è $\{0, 0, 2, 3, 4\}$. Può essere partizionato in $\{0, 2, 4\} + \{0, 3\}$, quindi la risposta è YES.
Per l'ultima query, il multinsieme di carte nell'intervallo è $\{1, 4\}$. Esso forma esattamente un pacchetto di carte standard di Tipo 2, quindi la risposta è YES.