G. Same Sum
time limit per test
6 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo is working with an integer sequence $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$. He must process $$$q$$$ queries in order. Each query is of one of the following two types:

  • 1 $$$L$$$ $$$R$$$ $$$v$$$ ($$$1 \le L \le R \le n$$$, $$$0 \le v \le 2 \cdot 10^5$$$): for all $$$i \in [L,R]$$$, update $$$a_i \gets a_i + v$$$;
  • 2 $$$L$$$ $$$R$$$ ($$$1 \le L \lt R \le n$$$, $$$R-L+1$$$ is even): determine if elements $$$a_L, a_{L+1}, \ldots, a_R$$$ can be divided into $$$(R-L+1)/2$$$ pairs of integers with the same sum.

Your task is to help Bobo process these queries efficiently.

Input

The first line of input contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$).

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$).

Then $$$q$$$ lines follow. Each of the following lines contains a query, described in the statement.

Output

For each query of the second type, output "YES" (without quotes) in one line if elements $$$a_L, a_{L+1}, \ldots, a_R$$$ can be divided into $$$(R-L+1)/2$$$ pairs of integers with the same sum; otherwise, output "NO" (without quotes) in one line.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes", and "Yes" will all be recognized as a positive response).

Example
Input
8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8
Output
YES
NO
YES