题目描述

给定两个互质的正整数 $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。