题目背景

这题跟 MC 有关的就是题目背景出现了三次 MC，提示说明出现了一次 MC。

           ▃▆█▇▄▖
       ▟◤▖　　　  ◥█  
   ◢◤ 　  ◢▐　　     ▐▉
 ▗◤　  　   ▂ ▗▖　 ▕ █▎
 ◤　▗▅▖ ◥▄　 ▀▀▀◣　█▊
▐　▕▎  ◥▖◣◤　 　　◢██
█◣　◥▅█▀　     　▐███◤
▐█▙▂　　　      ◢███◤
　◥██◣　　　　 ◢▄◤
　　　▀██▅▇▀▎▇

题目描述

对于两个序列 $a,b$，如果满足：

那么我们称 $a$ 比 $b$ 屑（$n$ 为 $a$ 的长度，$m$ 为 $b$ 的长度）。

如果对于一个序列 $a$，它比它的所有后缀都屑，那么我们称这个序列为先辈。

给定一个长为 $n$ 的序列 $a_i$，共有 $k$ 次操作，包括以下两种：

• 1 l r x 区间 $[l,r]$ 加上 $x$。
• 2 l r 查询区间 $[l,r]$ 是不是先辈。

输入格式

第一行两个整数 $n,k$ 代表序列长度与操作数。
第二行 $n$ 个整数 $a_i$ 代表数列每一项的值。
接下来 $k$ 行每行首先三个整数 $opt,l,r$：

• 如果 $opt=1$，接下来一个整数 $x$ 代表操作 $1$。
• 如果 $opt=2$，代表操作 $2$。

由于数据故障，$r$ 可能取到 $n+1$，请在这类情况下自行令 $r=n$，谢谢。

输出格式

对于每个操作 $2$，输出询问结果。

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

提示

样例说明

对于样例 $1$：

1. 询问区间 $[1,3]$ 是否为先辈，不是，输出 No。
2. 区间 $[3,4]$ 加上 $9$，现在序列为 $\{1,9,10,18,8,1,0\}$。
3. 询问区间 $[1,4]$ 是否为先辈，是，输出 Yes。
4. 区间 $[5,6]$ 加上 $11$，现在序列为 $\{1,9,10,18,19,12,0\}$。
5. 询问区间 $[2,6]$ 是否为先辈，不是，输出 No。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（1 pts）$\ \$：询问操作的区间长度均为 $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）：只有查询操作。
• Subtask 5（10 pts）：修改操作的数量不超过 $100$。
• Subtask 6（20 pts）：$n,k \le 10^5$。
• Subtask 7（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,k \le 10^6$，$|a_i|,|x| \le 10^9$。

本题强制 $O2$ 优化。

说明

Minecraft OI Round 2 C

• Maker：happydef
• Tester：tarjin