题目背景

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

题目描述

维护一个动态字符串 $s_{1..n}$，字符串的字符集是所有 $|x| \leq 10 ^ 9$ 的整数。要求支持两个操作：

1. 输入 $l, r, d$，对于所有 $l \leq i \leq r$，将 $s_i$ 修改为 $s_i + d$，注意 $d$ 可能是负数。

2. 输入 $l, r$，输出子串 $s_{l..r}$ 的字典序最小的后缀的起点位置。即，如果最小后缀是 $s_{p..r}$（$l\leq p\leq 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

提示

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

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