Codeforces Global Round 23 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

hashing

probabilities

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Kazaee

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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).

Input

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$$$).

Output

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

Example

Input

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

Output

NO

YES

NO

YES

YES

Note

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".

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 22:08:22 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|