U205696 距离和 Excellent Position

请你维护一个长度为 $n$ 的序列 $a$，支持两种操作： 1. 给出 $l$，$r$ 和 $x$，将区间 $[l, r]$ 内的每个数都加上 $x$，格式为 `1 l r x`。 2. 给出 $l$ 和 $r$，请你求出 $$\min^{r}_{x = l}\{\sum_{i = l}^r a_i |i - x|\}$$ 的值，格式为 `2 l r`。

**本题要求强制在线。** 第一行两个整数 $n$，$m$。 第二行 $n$ 个整数 $a$。 接下来 $m$ 行，每行一个操作，格式如题目描述。 设上一次操作 $2$ 的答案为 $lst$（初始时 $lst=0$），则 $x$ 的解密方式为 $(lst \bmod (10^6 + 1)) + x $，其他的值不加密。

为了减少输出量，你只需要输出最后一个操作 $2$ 的答案。

**【样例 1 解释】** 加密前的样例输入是这样的： ```plain 5 4 1 1 1 1 1 2 1 5 1 5 5 1 2 1 5 2 5 5 ``` 加密前的样例输出是这样的： ```plain 6 8 0 ``` 第一次询问时，$a=\{1,1,1,1,1\}$，$x=3$ 最优。 第二次询问时，$a=\{1,1,1,1,2\}$，$x=3$ 或 $x=4$ 最优。 第三次询问时，$a=\{1,1,1,1,2\}$，$x=5$ 最优。 **【数据范围】** **本题采取捆绑测试。** | 子任务编号 | 分数 | 特殊性质 | | :-: | :-: | :-: | | $1$ | $10$ | $n, m \le 100$ | | $2$ | $20$ | $n, m \le 5 \times 10^3$，时间限制为 $500 \, \text{ms}$ | | $3$ | $30$ | $n, m \le 10^5$ | | $4$ | $40$ | 时间限制为 $1.5 \, \text{s}$ | 对于 $100\%$ 的数据，$1 \le l \le r \le n \le 5 \times 10^5$，$1 \le m \le 5 \times 10^5$，解密后 $|x| \le 10^6$，保证 $a_i$ 始终大于 $0$ 且小于等于 $10^6$，除 Subtask2 与 Subtask4，其他子任务时间限制为 $1 \, \text{s}$。