字符串

题目描述

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

维护一个动态字符串 s[1..n]，字符串的字符集是所有 |x| ≤ 10⁹ 的整数。

要求支持两个操作： 

1) 输入 l, r, d，对于所有 l ≤ i ≤ r，将 s[i] 修改为 s[i] + d，注意 d 可能是负数。 

2) 输入 l, r，输出子串 s[l..r] 的字ި典序最小的后缀的起点位置。即，如果最小后缀是 s[p..r],(l ≤ p ≤ r)，请输出 p。 

输入说明

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

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

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

输出说明

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

样例

输入

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

输出

3
5
1

提示