您有一个由 $$$n$$$ 正整数组成的数组 $$$a$$$,并且您必须处理以下类型的 $$$q$$$ 查询:
- $$$1$$$ $$$i$$$ $$$x$$$: 将 $$$a_{i}$$$ 更改为 $$$x$$$,
- $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$:检查子数组 $$$a_{l}, a_{l+1}, \ldots a_{r}$$$ 中每个正整数的出现次数是否是 $$$k$$$ 的倍数(检查示例以更好地理解)。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n , q \le 3 \cdot 10^5$$$)、$$$a$$$ 的长度和查询次数。
下一行包含 $$$n$$$ 整数 $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$) — $$$a$$$ 的元素。
接下来的 $$$q$$$ 行描述一个查询。它具有以下形式之一。
- $$$1$$$ $$$i$$$ $$$x$$$, ($$$1 \le i \le n$$$ , $$$1 \le x \le 10^9$$$), 或
- $$$2$$$ $$$l$$$ $$$r$$$ $$$k$$$, ($$$1 \le l \le r \le n$$$ , $$$1 \le k \le n$$$)。
输出
对于第二类型的每个查询,如果查询的答案为是,则打印“YES”,否则打印“NO”。
示例
输入 #1
10 8 1234 2 3 3 2 1 1 2 3 4 2 1 6 2 1 1 1 2 1 6 2 2 1 9 2 1 10 5 2 1 9 3 1 3 5 2 3 10 2
输出 #1
NO YES NO YES YES
注意
在第一个查询中,请求的子数组是$$$[1234, 2, 3, 3, 2, 1]$$$,显然$$$1$$$出现的次数不能被$$$k = 2$$$整除。所以答案是“不”。
在第三个查询中,请求的子数组为$$$[1, 2, 3, 3, 2, 1]$$$,可以看出该子数组中每个整数出现的次数可以被$$$k = 2$$$整除。所以答案是“是”。
在第六个查询中,请求的子数组为$$$[1, 2, 3, 3, 2, 1, 1, 2, 3]$$$,可以看出该子数组中每个整数出现的次数可以被$$$k = 3$$$整除。所以答案是“是”。