Se te dan dos enteros positivos coprimos $p$ y $q$. Hay $pq$ tipos diferentes de cartas, numerados $0, 1, \ldots, pq - 1$.
Hay dos tipos de paquetes de cartas estándar:
- Paquetes de cartas estándar de tipo 1: hay $p$ clases, numeradas por $u$ ($0 \le u < p$). El paquete numerado $u$ contiene una copia de cada carta cuyo número satisface $x \equiv u \pmod{p}$, por lo que cada paquete contiene exactamente $q$ cartas.
- Paquetes de cartas estándar de tipo 2: hay $q$ clases, numeradas por $v$ ($0 \le v < q$). El paquete numerado $v$ contiene una copia de cada carta cuyo número satisface $x \equiv v \pmod{q}$, por lo que cada paquete contiene exactamente $p$ cartas.
Ahora hay $n$ cartas dispuestas sobre la mesa, donde el número de la $i$-ésima carta es $a_i$. Debes procesar $Q$ operaciones de los dos tipos siguientes:
1 i x: reemplaza el número de la $i$-ésima carta por $x$;2 l r: determina si todas las cartas en el intervalo $[l, r]$ pueden particionarse exactamente en varios paquetes de cartas estándar.
Nota: Al reempaquetar las cartas, cada carta en el intervalo debe pertenecer a exactamente un paquete, y cada clase de paquete de cartas estándar puede utilizarse cualquier número de veces.
Entrada
La primera línea contiene cuatro enteros $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 segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), que indican el número inicial de cada carta.
Las siguientes $Q$ líneas describen cada una una operación de la forma 1 i x o 2 l r:
- Para cada operación del primer tipo, se garantiza que $1 \le i \le n$ y $0 \le x < pq$.
- Para cada operación del segundo tipo, se garantiza que $1 \le l \le r \le n$.
Salida
Para cada operación del segundo tipo, si las cartas especificadas pueden particionarse exactamente en varios paquetes de cartas estándar, imprime YES; de lo contrario, imprime NO.
Ejemplos
Entrada 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
Salida 1
YES NO NO YES
Nota
Cuando $p = 2, q = 3$:
- Hay dos paquetes de cartas estándar de tipo 1: $\{0, 2, 4\}$ y $\{1, 3, 5\}$.
- Hay tres paquetes de cartas estándar de tipo 2: $\{0, 3\}$, $\{1, 4\}$ y $\{2, 5\}$.
Para la primera consulta, el multiconjunto de cartas en el intervalo es $\{0, 0, 2, 3, 4\}$. Puede particionarse en $\{0, 2, 4\} + \{0, 3\}$, por lo que la respuesta es YES.
Para la última consulta, el multiconjunto de cartas en el intervalo es $\{1, 4\}$. Forma exactamente un paquete de cartas estándar de tipo 2, por lo que la respuesta es YES.