Problem 28476 --字符串

28476: 字符串

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 3  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS0元][添加到购物车][下载测试数据0元][7570kb]

Description

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

维护一个动态字符串 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。 

Input

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

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

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

Output

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

Sample 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

Sample Output

3
5
1

HINT

Source

[Submit][Status]