On vous donne deux entiers strictement positifs premiers entre eux $p$ et $q$. Il existe $pq$ types différents de cartes, numérotés $0, 1, \ldots, pq - 1$.
Il existe deux types de paquets de cartes standards :
- Paquets de cartes standards de type 1 : il en existe $p$ sortes, numérotées par $u$ ($0 \le u < p$). Le paquet numéroté $u$ contient un exemplaire de chaque carte dont le numéro vérifie $x \equiv u \pmod{p}$, de sorte que chaque paquet contient exactement $q$ cartes.
- Paquets de cartes standards de type 2 : il en existe $q$ sortes, numérotées par $v$ ($0 \le v < q$). Le paquet numéroté $v$ contient un exemplaire de chaque carte dont le numéro vérifie $x \equiv v \pmod{q}$, de sorte que chaque paquet contient exactement $p$ cartes.
Il y a maintenant $n$ cartes disposées sur la table, où le numéro de la $i$-ème carte est $a_i$. Vous devez traiter $Q$ opérations des deux types suivants :
1 i x: remplacer le numéro de la $i$-ème carte par $x$ ;2 l r: déterminer si toutes les cartes de l'intervalle $[l, r]$ peuvent être partitionnées exactement en plusieurs paquets de cartes standards.
Remarque : Lors du reconditionnement des cartes, chaque carte de l'intervalle doit appartenir à exactement un paquet, et chaque sorte de paquet de cartes standard peut être utilisée un nombre quelconque de fois.
Entrée
La première ligne contient quatre entiers $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 deuxième ligne contient $n$ entiers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), désignant le numéro initial de chaque carte.
Les $Q$ lignes suivantes décrivent chacune une opération sous la forme 1 i x ou 2 l r :
- Pour chaque opération du premier type, il est garanti que $1 \le i \le n$ et $0 \le x < pq$.
- Pour chaque opération du second type, il est garanti que $1 \le l \le r \le n$.
Sortie
Pour chaque opération du second type, si les cartes spécifiées peuvent être partitionnées exactement en plusieurs paquets de cartes standards, affichez YES ; sinon, affichez NO.
Exemples
Entrée 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
Sortie 1
YES NO NO YES
Remarque
Lorsque $p = 2, q = 3$ :
- Il existe deux paquets de cartes standards de type 1 : $\{0, 2, 4\}$ et $\{1, 3, 5\}$.
- Il existe trois paquets de cartes standards de type 2 : $\{0, 3\}$, $\{1, 4\}$ et $\{2, 5\}$.
Pour la première requête, le multiensemble de cartes dans l'intervalle est $\{0, 0, 2, 3, 4\}$. Il peut être partitionné en $\{0, 2, 4\} + \{0, 3\}$, donc la réponse est YES.
Pour la dernière requête, le multiensemble de cartes dans l'intervalle est $\{1, 4\}$. Il forme exactement un paquet de cartes standard de type 2, donc la réponse est YES.