You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定两个互质的正整数 $p$ 和 $q$。现有 $pq$ 种不同的卡片，编号分别为 $0, 1, \ldots, pq-1$。

游戏中有两类标准卡包：

• 第一类标准卡包：共有 $p$ 种，编号为 $u \ (0 \le u < p)$。编号为 $u$ 的卡包内包含所有编号满足 $x \equiv u \pmod p$ 的卡片各一张（每包共 $q$ 张）。
• 第二类标准卡包：共有 $q$ 种，编号为 $v \ (0 \le v < q)$。编号为 $v$ 的卡包内包含所有编号满足 $x \equiv v \pmod q$ 的卡片各一张（每包共 $p$ 张）。

现在桌面上排列着 $n$ 张卡片，第 $i$ 张卡片的编号为 $a_i$。你需要处理 $Q$ 次操作，操作分为以下两种：

• 1 i x：将第 $i$ 张卡片的编号替换为 $x$。
• 2 l r：判断区间 $[l, r]$ 内的这些卡片，能否恰好被划分成若干个标准卡包。

注：在重新打包时，区间内的每一张卡片都必须恰好被分入一个卡包中，每一种标准卡包都可以被使用任意多次。

输入格式

第一行包含四个整数 $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)$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \le a_i < pq)$，表示初始时每张卡片的编号。

接下来 $Q$ 行，每行描述一次操作，格式为 1 i x 或 2 l r：

• 对于所有第一类操作，保证 $1 \le i \le n$，$0 \le x < pq$。
• 对于所有第二类操作，保证 $1 \le l \le r \le n$。

输出格式

对于每一次 2 l r 操作，如果指定的卡片可以恰好被划分成若干个标准卡包，输出一行 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,2,4\}, \{1,3,5\}$。
• 第二类标准卡包有三种，分别为：$\{0,3\}, \{1,4\}, \{2,5\}$。

对于第一次询问，区间内的卡片构成的多重集为 $\{0,0,2,3,4\}$，它可以被拆分为 $\{0,2,4\} + \{0,3\}$，因此输出 YES。 对于最后一次询问，区间内的多重集为 $\{1,4\}$，它恰好构成了一个第二类标准卡包，因此输出 YES。