CF1746F.Kazaee

You have an array $a$ consisting of $n$ positive integers and you have to handle $q$ queries of the following types:

• $1$ $i$ $x$: change $a_{i}$ to $x$,
• $2$ $l$ $r$ $k$: check if the number of occurrences of every positive integer in the subarray $a_{l}, a_{l+1}, \ldots a_{r}$ is a multiple of $k$ (check the example for better understanding).

你有一个由 $n$ 个正整数组成的数组 $a$，需要处理 $q$ 个如下类型的查询：

• $1$ $i$ $x$：将 $a_{i}$ 修改为 $x$；
• $2$ $l$ $r$ $k$：检查子数组 $a_{l}, a_{l+1}, \ldots, a_{r}$ 中每个正整数的出现次数是否均为 $k$ 的倍数（参见示例以更好理解）。

The first line of the input contains two integers $n$ and $q$ ($1 \le n , q \le 3 \cdot 10^5$), the length of $a$ and the number of queries.

Next line contains $n$ integers $a_{1}, a_{2}, \ldots a_{n}$ ($1 \le a_{i} \le 10^9$) — the elements of $a$.

Each of the next $q$ lines describes a query. It has one of the following forms.

• $1$ $i$ $x$, ($1 \le i \le n$ , $1 \le x \le 10^9$), or
• $2$ $l$ $r$ $k$, ($1 \le l \le r \le n$ , $1 \le k \le n$).

输入的第一行包含两个整数 $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$）。

For each query of the second type, if answer of the query is yes, print "YES", otherwise print "NO".

对于每个第二类查询，如果查询的答案为“是”，则输出 “YES”，否则输出 “NO”。

In the first query, requested subarray is $[1234, 2, 3, 3, 2, 1]$, and it's obvious that the number of occurrence of $1$ isn't divisible by $k = 2$. So the answer is "NO".

In the third query, requested subarray is $[1, 2, 3, 3, 2, 1]$, and it can be seen that the number of occurrence of every integer in this sub array is divisible by $k = 2$. So the answer is "YES".

In the sixth query, requested subarray is $[1, 2, 3, 3, 2, 1, 1, 2, 3]$, and it can be seen that the number of occurrence of every integer in this sub array is divisible by $k = 3$. So the answer is "YES".

在第一次查询中，所请求的子数组为 $[1234, 2, 3, 3, 2, 1]$，显然数字 $1$ 的出现次数不能被 $k = 2$ 整除。因此答案为 “NO”。

在第三次查询中，所请求的子数组为 $[1, 2, 3, 3, 2, 1]$，可以看出该子数组中每个整数的出现次数均可被 $k = 2$ 整除。因此答案为 “YES”。

在第六次查询中，所请求的子数组为 $[1, 2, 3, 3, 2, 1, 1, 2, 3]$，可以看出该子数组中每个整数的出现次数均可被 $k = 3$ 整除。因此答案为 “YES”。