K. Optimism
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
"It's all part of my master plan"

Now that Technoblade has built his potato empire and taken a vacation to rest, he has decided to just observe the performance of his plantation. Techno has $$$N$$$ plots, numbered from 1 to $$$n$$$. For each plot, its land is worth a price that depends on the weather, type of soil, soil erosion, level of rain, etc.

To stay updated, he first made a list of land values: $$$V_1, V_2... V_n$$$, with $$$V_i$$$ being the price of the $$$i$$$-th plot. After that, he observed that weather effects affect a continuous segment of plots at a time, adding or subtracting from the plot value. Therefore, you must respond to two types of operations:

  • Type 1: this is the operation of adding to the plot values. It has the format $$$1\ l\ r\ x$$$. With this operation, $$$V_i := V_i + x$$$ for all $$$l \leq i \leq r$$$. It is guaranteed that $$$-10^6 \leq x \leq 10^6$$$.
  • Type 2: It has the format $$$2\ l\ r$$$. This is a query operation, in which you must print the sum of the optimistic values of the plots from index $$$l$$$ to $$$r$$$. The optimistic value of the plot is the highest value it has ever had.

For example, if $$$V = \{ 1,2,3\}$$$ and a type $$$1$$$ operation $$$1\ 2\ 2\ -2$$$ occurs, that is, $$$l=2,r=2$$$ adding $$$x=-2$$$ we have that $$$V = \{1,0,3\}$$$. In addition, $$$V_{optimistic} = \{1,2,3\}$$$ because the highest value that $$$V_2$$$ has ever had is $$$2$$$.

Input

The first line has two integers $$$n$$$ and $$$q$$$, representing the number of plots and the number of operations. It is guaranteed that $$$1 \leq n,q \leq 3 \cdot 10^5$$$.

Followed by a line with $$$n$$$ integers $$$V_i$$$, $$$1 \leq V_i \leq 10^6$$$.

Finally, there are $$$q$$$ lines with type 1 or type 2 operations. Type 1 operations have the format $$$1\ l\ r x$$$ and type 2 operations have the format $$$2\ l\ r$$$. It is guaranteed that $$$1 \leq l \leq r \leq n$$$ and $$$-10^6 \leq x \leq 10^6$$$.

Output

For each type 2 query, print the sum of the optimistic values of the plots from number $$$l$$$ to $$$r$$$.

Examples
Input
1 5
1
1 1 1 99
1 1 1 -99
2 1 1
1 1 1 100
2 1 1
Output
100
101
Input
4 8
1 2 3 4
2 1 4
1 1 4 -1
2 1 4
1 1 3 2
2 3 3
1 1 3 5
1 1 3 -100
2 3 3
Output
10
10
4
9
Note

The prices of the plot can become negative, which means that the plot sucks so much he would pay for someone to buy it.