A85768.「ZJOI2017」字符串

猪小侠最近学习了字符串相关理论，现在他遇到了这样一个题：

维护一个动态字符串 $s[1..n]$ ，字符串的字符集是所有 $|x| ≤ 10^9$ 的整数。要求支持两个操作：

• 输入 $l, r, d$ ，对于所有 $l ≤ i ≤ r$ ，将 $s[i]$ 修改为 $s[i] + d$ ，注意 $d$ 可能是负数。
• 输入 $l, r$ ，输出子串 $s[l..r]$ 的字ި序最小的后缀的起点位置。即，如果最小后缀是 $s[p..r],(l ≤p ≤ r)$ ，请输出 $p$ 。

第一行两个非负整数 $n, q$ 。

接下来一行包含 $n$ 个正整数，表示初始时的字符串。

接下来 $q$ 行，每行为 $1$ $l$ $r$ $d$ 或 $2$ $l$ $r$ ，分别表示两种操作。

对于所有的查询操作按顺序输出答案。

测试点编号	n	m	其他约定
1	$≤ 300$	$≤ 300$	无
2	$≤ 2 × 10^4$	$≤10^4 $	无
3	$≤ 2 × 10^4$	$≤10^4 $	无
4	$≤ 2 × 10^5$	$3×10^4$	只有第二类操作
5	$≤ 2 × 10^5$	$3×10^4$	只有第二类操作
6	$≤ 2 × 10^5$	$3×10^4$	数据随机生成
7	$≤ 2 × 10^5$	$3×10^4$	数据随机生成
8	$≤ 2 × 10^5$	$3×10^4$	无
9	$≤ 2 × 10^5$	$3×10^4$	无
10	$≤ 2 × 10^5$	$3×10^4$	无

对于 $100\%$ 的数据， $1 ≤ l ≤ r ≤ n$ ， $|d| ≤ 10^3$ ， $|s_i| ≤ 10^8$ 。

注意，$6$ 和 $7$ 两个测试数据在随机生成时， $s_i$ 在 $[0, 1]$ 中随机， $d$ 在 $±1$ 中随机。操作种类和操作区间都是等概率随机的。