J. Portals in Narxoz
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At Narxoz University, the faculties are not just departments — they're part of a living, evolving structure.

There are $$$n$$$ faculties, arranged in a circular building. That means faculty $$$0$$$ is a neighbor of $$$n - 1$$$. Each faculty has a type — maybe it's economics, business, or even magic accounting — and each type is represented by an integer.

The university is equipped with high-tech portals that let you instantly travel between any two faculties of the same type.

But sometimes that's not enough. So you're allowed to build corridors between neighboring faculties — that is, between faculty $$$i$$$ and $$$(i + 1)$$$ $$$mod$$$ $$$n$$$. Once built, you can walk back and forth through them.

Also, faculties love to rebrand themselves. A faculty can suddenly change its type (maybe they switched to crypto-finance).

You'll receive $$$q$$$ requests — each being one of the following:

  • $$$1$$$ $$$i$$$ $$$x$$$ — Faculty $$$i$$$ changes its type to $$$x$$$.

  • $$$2$$$ $$$i$$$ — A corridor is built between faculty $$$i$$$ and $$$i + 1$$$ $$$mod$$$ $$$n$$$.

  • $$$3$$$ $$$a$$$ $$$b$$$ — Check if you can travel from faculty $$$a$$$ to faculty $$$b$$$ using any number of corridors or portals.

Your task is to answer for each query of type 3, print YES if such travel is possible, or NO otherwise.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ — the number of faculties and the number of queries, respectively ($$$1 \le n, q \le 10^5$$$).

The second line contains $$$n$$$ integers: $$$t_0, t_1, ..., t_{n-1}$$$ — the initial types of the faculties ($$$0 \le t_i \lt 10^{18}$$$).

Each of the following $$$q$$$ lines describes a query in one of the following formats:

  • $$$1$$$ $$$i$$$ $$$x$$$ ($$$0 \le i \lt n, 0 \le x \lt 10^{18}$$$)
  • $$$2$$$ $$$i$$$ ($$$0 \le i \lt n$$$)
  • $$$3$$$ $$$a$$$ $$$b$$$ ($$$0 \le a \le b \lt n$$$)

All queries of type $$$2$$$ are unique.

Output

For each query of type $$$3$$$, print YES if $$$b$$$ can be reached from $$$a$$$ , otherwise NO.

Examples
Input
3 3
0 0 2
2 2
3 0 2
1 0 0
Output
YES
Input
10 9
2 1 0 1 2 1 2 0 2 2
2 6
1 5 3
2 5
1 5 4
3 0 6
1 9 3
2 2
2 7
3 9 3
Output
YES
NO