Description

For two sequences $a,b$, if the following holds:

then we say that $a$ is "worse" than $b$ ($n$ is the length of $a$, and $m$ is the length of $b$).

If for a sequence $a$, it is "worse" than all of its suffixes, then we call this sequence an ancestor.

Given a sequence $a_i$ of length $n$, there are $k$ operations, of the following two types:

• 1 l r x Add $x$ to the interval $[l,r]$.
• 2 l r Query whether the interval $[l,r]$ is an ancestor.

Input Format

The first line contains two integers $n,k$, representing the sequence length and the number of operations.
The second line contains $n$ integers $a_i$, representing the value of each element.
The next $k$ lines each start with three integers $opt,l,r$:

• If $opt=1$, then an integer $x$ follows, representing operation $1$.
• If $opt=2$, it represents operation $2$.

Due to a data failure, $r$ may be $n+1$. In such cases, please set $r=n$ by yourself. Thank you.

Output Format

For each operation $2$, output the query result.

7 5
1 9 1 9 8 1 0
2 1 3
1 3 4 9
2 1 4
1 5 6 11
2 2 6

No
Yes
No

Hint

Sample Explanation

For Sample $1$:

1. Query whether interval $[1,3]$ is an ancestor. It is not, output No.
2. Add $9$ to interval $[3,4]$. Now the sequence is $\{1,9,10,18,8,1,0\}$.
3. Query whether interval $[1,4]$ is an ancestor. It is, output Yes.
4. Add $11$ to interval $[5,6]$. Now the sequence is $\{1,9,10,18,19,12,0\}$.
5. Query whether interval $[2,6]$ is an ancestor. It is not, output No.

Constraints and Conventions

This problem uses bundled testdata.

• Subtask 1 (1 pts) $\ \$: The interval length of every query operation is $1$.
• Subtask 2 (9 pts) $\ \$: $n,k \le 10^3$.
• Subtask 3 (10 pts): $n,k\le 5\times 10^3$.
• Subtask 4 (10 pts): Only query operations.
• Subtask 5 (10 pts): The number of update operations does not exceed $100$.
• Subtask 6 (20 pts): $n,k \le 10^5$.
• Subtask 7 (40 pts): No special restrictions.

For $100\%$ of the testdata, $1 \le n,k \le 10^6$, $|a_i|,|x| \le 10^9$.

This problem enforces $O2$ optimization.

Notes

Minecraft OI Round 2 C

• Maker: happydef
• Tester: tarjin

Translated by ChatGPT 5