[ZJOI2017]字符串
题号：NC20527
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

猪小侠最近学习了字符串相关理论，现在他遇到了这样一个题： 维护一个动态字符串 s[1…n]s[1…n]，字符串的字符集是所有 |x|≤109|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，分别表示两种操作。

输出描述:

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

输入

复制 
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

备注:

对于 100% 的数据，1 ≤ l ≤ r ≤ n，|d| ≤103，|si| ≤ 108。 注意,6和7两个测试数据在随机生成时，si在 [0, 1]中随机，d在±1中随机。操作种类和操作区间都是等概率随机的。