K. Card Packs
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

There are two types of standard card packs:

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

There are now $$$n$$$ cards arranged on the table, where 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 all cards in the interval $$$[l,r]$$$ can be partitioned exactly into several standard card packs.

Note: When repacking the cards, every card in the interval must belong to exactly one pack, and each kind of standard card pack may be used any number of times.

Input

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 \lt pq$$$), denoting the initial number of each card.

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

  • For every operation of the first type, it is guaranteed that $$$1\le i\le n$$$ and $$$0\le x \lt pq$$$.
  • For every operation of the second type, it is guaranteed that $$$1\le l\le r\le n$$$.
Output

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

Example
Input
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
YES
NO
NO
YES
Note

When $$$p=2,q=3$$$:

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

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

For the last query, the multiset of cards in the interval is $$$\{1,4\}$$$. It forms exactly one Type-2 standard card pack, so the answer is YES.