题目背景

秋静叶是在秋季掌管落叶的神明。在秋季即将迎来落幕之时，因她的力量使然，山里会变得火红一片。同时，将红叶变为落叶也是她工作的一环。

秋穰子是在秋季掌管丰收的神明。与秋静叶的职责相反，她掌管着秋天果实的成熟、秋粮的收获。

交织着快乐与忧愁的秋天，怎能让人不有感而发呢？

题目描述

秋穰子和秋静叶是掌管秋天的神灵，因而控制着田地的收成。具体而言，有 $n$ 块田依次排列，第 $i$ 块田的丰收程度为 $a_i$。秋之姐妹会据此得出一年的年成。

在综合考察了各方面因素后，秋之姐妹得出了收获第 $l$ 块至第 $r$ 块田地可以获得的作物总量 $\Omega(l,r)$。具体定义如下：

$$\begin{aligned} \Alpha(l,r)&=\max_{i=l}^r\{i\times[a_i=\max_{j=l}^r\{a_j\}]\}\cr \Beta(l,r)&=\max_{i=l}^r\{\min_{j=1}^i\{\Alpha(j,i)\}\}-\min_{i=l}^r\{\max_{j=1}^i\{\Alpha(j,i)\}\}\cr \Omega(l,r)&=\min_{i=l}^r\{\min_{j=i}^r\{|\Beta(i,j)|\}\} \end{aligned}$$

在提示说明部分有相关符号的解释。

---

由于相关因素的影响，田地的丰收程度会发生变化。因此秋之姐妹会对 $a$ 进行 $q$ 次操作：

1. 形如 $\colorbox{f0f0f0}{\verb!1 x y!}$，表示让 $a_1,a_{2},a_{3},\cdots ,a_x$ 分别加上 $y$。
2. 形如 $\colorbox{f0f0f0}{\verb!2 l r!}$，表示询问 $\Omega(l,r)$ 的值。

输入格式

• 第一行有两个正整数 $n,q$，分别表示田地总数、操作次数。
• 接下来一行有 $n$ 个整数，表示每块田地的丰收程度。
• 接下来 $q$ 行，第一个数字 $op$ 表示该操作的种类。
  • 如果 $op=1$，那么接下来会有两个整数 $x,y$，含义如题意所示。
  • 如果 $op=2$，那么接下来会有两个正整数 $l,r$，含义如题意所示。

输出格式

• 输出若干行。对于每一个操作 $2$，输出对应的结果。

6 3
1 1 4 5 1 4
2 3 5
1 2 5
2 3 5

0
1

10 6
1 3 5 7 8 12 14 15 17 18
2 5 9
1 3 10
2 4 5
1 1 10
2 4 6
2 1 10

0
1
3
0

提示

样例 $3$ 见下发的附件 $\textbf{\textit{sequence3.in}}/\textbf{\textit{sequence3.ans}}$。

数据范围及约定

$$\def{\arraystretch}{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,q\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 100 & - & 10\cr\hline 2 & 5\times 10^3 & - &15\cr\hline 3 & 10^5 & \text{A} &10\cr\hline 4 & 10^5 & \text{B} &5\cr\hline 5 & 10^5 & - &30\cr\hline 6 & 6\times 10^6 & - & 30\cr\hline \end{array} $$

特殊性质 $\textbf{A}$：保证对于任意的 $i\in[1,n-1]$，都有 $a_i<a_{i+1}$。
特殊性质 $\textbf{B}$：保证没有操作 $1$。

对于全部数据，保证 $1 \leq n,q \leq 6\times10^6$，$a_i,y_i\in[0,10^9]$，$1\le x_i\le n$，$1\le l_i\le r_i \le n$。

符号解释

• $[P]$ 是艾弗森括号，其中 $P$ 是一个条件。如果 $P$ 为真，则该式子的值为 $1$；否则为 $0$。也就是说，

$$[P]=\begin{cases}1 & \text{$P$ 为真}\cr 0 & \text{$P$ 为假}\end{cases} $$

• $\min\limits_{i=l}^r\{P\}$ 表示当 $i$ 取 $l,l+1,l+2,\cdots,r$ 时，表达式 $P$ 的取值的最小值；同理定义了 $\max\limits_{i=l}^r\{P\}$。

提示

本题输入输出量较大，请注意常数因子的影响。