猪小侠最近学习了字符串相关理论，现在他遇到了这样一个题： 维护一个动态字符串 $s[1\dots n]$，字符串的字符集是所有 $|x|\le {10}^9$ 的整数。要求支持两个操作：

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

输入格式

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

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

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

输出格式

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

样例一

input

5 5
3 2 1 4 3
2 1 5
1 2 4 2
2 1 5
1 2 5 1
2 1 5

output

3
5
1

样例二

见样例数据下载。

限制与约定

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

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

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载