Problem Description

You are given two coprime positive integers $p$ and $q$. There are $pq$ different cards, numbered $0,1,\ldots,pq-1$.

In the game, there are two types of standard card packs:

• Type 1 standard packs: there are $p$ kinds, labeled $u$ ($0\le u<p$). Pack $u$ contains exactly one copy of every card whose number satisfies $x\equiv u\pmod p$ (so each pack has $q$ cards).
• Type 2 standard packs: there are $q$ kinds, labeled $v$ ($0\le v<q$). Pack $v$ contains exactly one copy of every card whose number satisfies $x\equiv v\pmod q$ (so each pack has $p$ cards).

Now there are $n$ cards laid out on the table, and the number of the $i$-th card is $a_i$. You need to process $Q$ operations of the following two types:

• 1 i x: replace the number of the $i$-th card with $x$.
• 2 l r: determine whether the cards in the interval $[l,r]$ can be partitioned exactly into several standard card packs.

Note: When repacking, every card in the interval must be placed into exactly one pack. Each kind of standard pack may be used any number of times.

Input Format

The first line contains four integers $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$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i<pq$), representing the initial number of each card.

The next $Q$ lines each describe one operation, in the format 1 i x or 2 l r:

• For all operations of the first type, it is guaranteed that $1\le i\le n$ and $0\le x<pq$.
• For all operations of the second type, it is guaranteed that $1\le l\le r\le n$.

Output Format

For each 2 l r operation, if the specified cards can be partitioned exactly into several standard card packs, output YES on one line; otherwise output NO on one line.

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

YES
NO
NO
YES

Hint

When $p=2,q=3$:

• There are two Type 1 standard packs: $\{0,2,4\},\{1,3,5\}$.
• There are three Type 2 standard packs: $\{0,3\},\{1,4\},\{2,5\}$.

For the first query, the multiset of cards in the interval is $\{0,0,2,3,4\}$. It can be split into $\{0,2,4\}+\{0,3\}$, so the output is YES.

For the last query, the multiset in the interval is $\{1,4\}$. It is exactly one Type 2 standard pack, so the output is YES.

Translated by ChatGPT 5