カードパック - Problem

互いに素な $2$ つの正の整数 $p$ と $q$ が与えられます。$0, 1, \ldots, pq - 1$ の番号が付けられた $pq$ 種類のカードがあります。

標準カードパックには次の $2$ つのタイプがあります：

タイプ 1 の標準カードパック：$u$（$0 \le u < p$）によって番号付けられた $p$ 種類があります。番号 $u$ のパックには、番号が $x \equiv u \pmod{p}$ を満たすすべてのカードが $1$ 枚ずつ含まれており、したがって各パックにはちょうど $q$ 枚のカードが含まれます。
タイプ 2 の標準カードパック：$v$（$0 \le v < q$）によって番号付けられた $q$ 種類があります。番号 $v$ のパックには、番号が $x \equiv v \pmod{q}$ を満たすすべてのカードが $1$ 枚ずつ含まれており、したがって各パックにはちょうど $p$ 枚のカードが含まれます。

現在、テーブルの上に $n$ 枚のカードが並べられており、$i$ 番目のカードの番号は $a_i$ です。以下の $2$ 種類の操作を $Q$ 回処理する必要があります：

注記： カードをパックに詰め直す際、区間内の各カードはちょうど $1$ つのパックに属さなければならず、各種類の標準カードパックは何回でも使用できます。

$1$ 行目には $4$ つの整数 $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$）が与えられます。

$2$ 行目には、各カードの初期番号を表す $n$ 個の整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < pq$）が与えられます。

続く $Q$ 行にはそれぞれ、1 i x または 2 l r の形式で操作が与えられます：

$2$ 番目のタイプの各操作について、指定されたカードをいくつかの標準カードパックにちょうど分割できる場合は YES を出力し、そうでない場合は NO を出力してください。

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

$p = 2, q = 3$ のとき：

最初のクエリでは、区間内のカードの多重集合は $\{0, 0, 2, 3, 4\}$ です。これは $\{0, 2, 4\} + \{0, 3\}$ に分割できるため、答えは YES です。

最後のクエリでは、区間内のカードの多重集合は $\{1, 4\}$ です。これはちょうど $1$ つのタイプ 2 の標準カードパックをなすため、答えは YES です。

QOJ.ac