1451 - 字符串

通过次数

0

提交次数

0

时间限制 : 5 秒
内存限制 : 512 MB

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

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

要求支持两个操作: 

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

来源

ZJOI2017 NOIP 省选 高级