P8010 "Wdsr-3" Sentimental Red Rain.

Shizuha Aki is the goddess who manages falling leaves in autumn. When autumn is about to end, due to her power, the mountains will turn completely fiery red. At the same time, turning red leaves into fallen leaves is also part of her job. Minoriko Aki is the goddess who manages harvest in autumn. Opposite to Shizuha Aki’s duty, she is in charge of the ripening of autumn fruits and the harvesting of autumn crops. In an autumn woven with happiness and sorrow, how can one not feel sentimental?

Minoriko Aki and Shizuha Aki are deities in charge of autumn, so they control the harvest of the fields. Specifically, there are $n$ fields arranged in order, and the harvest level of the $i$-th field is $a_i$. The Aki sisters will use this to determine how good the year’s harvest is. After considering various factors, the Aki sisters determined that harvesting fields $l$ through $r$ yields a total crop amount $\Omega(l,r)$. It is defined as follows: $$ \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}$$ There is an explanation of the related symbols in the **Hint** section. --- Due to certain factors, the harvest levels of the fields will change. Therefore, the Aki sisters will perform $q$ operations on $a$: 1. In the form $\colorbox{f0f0f0}{\verb!1 x y!}$, meaning to add $y$ to $a_1,a_{2},a_{3},\cdots ,a_x$ **respectively**. 2. In the form $\colorbox{f0f0f0}{\verb!2 l r!}$, meaning to query the value of $\Omega(l,r)$.

- The first line contains two positive integers $n,q$, representing the total number of fields and the number of operations. - The next line contains $n$ integers, representing the harvest level of each field. - The next $q$ lines: the first number $op$ indicates the type of the operation. - If $op=1$, then two integers $x,y$ follow, with the meaning as described. - If $op=2$, then two positive integers $l,r$ follow, with the meaning as described.

- Output several lines. For each operation $2$, output the corresponding result.

Sample $3$ can be found in the attached files $\textbf{\textit{sequence3.in}}/\textbf{\textit{sequence3.ans}}$. #### Constraints and Conventions $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,q\le} & \textbf{Special Property} & \textbf{Score}\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} $$ **Special Property** $\textbf{A}$: It is guaranteed that for any $i\in[1,n-1]$, we have $a_i