Problem Description

In his yard, Marko has built a histogram out of wooden columns: $n$ columns of width $1$ stand next to each other, and the column at position $i$ has height $h_i$. Marko likes to change his work, so sometimes he raises, lowers or replaces some of the columns.

Sometimes Marko looks only at a part of the histogram, the columns at positions from $l$ to $r$, and imagines a lot of rain falling on them. The columns outside the observed part do not exist at that moment, so water can flow away over the left edge of column $l$ and over the right edge of column $r$. The rain falls until the histogram is full: water stays wherever it is trapped by higher columns on both sides, and all other water flows away. One $1\times 1$ cell filled with water is one unit of water.

We say that a column is completely under water if there is water above its top. A column is not completely under water if its top is dry, that is, there is no water above it. Water may still touch such a column from the side, up to the height of its top.

Marko will make $q$ events in order, and each of them is of one of the following five types:

• 1 i x - the height of column $i$ becomes $x$,
• 2 l r x - the heights of all columns from $l$ to $r$ become $x$,
• 3 l r x - the heights of all columns from $l$ to $r$ increase by $x$ (the number $x$ may also be negative),
• 4 l r - Marko observes the columns from $l$ to $r$ and wants to know how many of them are not completely under water,
• 5 l r - Marko observes the columns from $l$ to $r$ and wants to know how many units of water in total are held.

Help Marko and answer all of his questions. Observing does not change the histogram, and the water disappears after each question.

Input Format

The first line contains positive integers $n$ and $q$ ($1\le n,q\le 200\,000$), the number of columns and the number of events.

The second line contains $n$ integers $h_1,h_2,\ldots,h_n$ ($0\le h_i\le 10^9$), the initial heights of the columns.

Each of the following $q$ lines contains the description of one event in one of the forms given above. It holds that $1\le i\le n$ and $1\le l\le r\le n$. In events of types $1$ and $2$, $0\le x\le 10^9$, and in events of type $3$, $-10^9\le x\le 10^9$.

It is guaranteed that the heights of all columns are integers between $0$ and $10^9$ at all times.

Output Format

For each event of type $4$ or $5$, in the order they are given, output the answer to Marko's question in a separate line.

8 6
3 0 2 4 1 4 0 2
4 1 8
4 2 5
4 3 3
4 5 8
4 1 4
4 2 7

4
4
1
3
2
5

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

6
3
1
0
1

5 8
2 0 1 0 3
5 1 5
4 1 5
3 2 4 2
5 1 5
2 1 3 1
5 1 5
1 4 5
4 1 5

5
2
1
0
5

Hint

Clarification of the first example

The histogram is $[3,0,2,4,1,4,0,2]$. In the first question, Marko observes the whole histogram. Water is held above columns $2$, $3$, $5$ and $7$ ($3$, $1$, $3$ and $2$ units, respectively), while the tops of columns $1$, $4$, $6$ and $8$ are dry. These four columns are not completely under water, so the answer is $4$.

In the second question, Marko observes the columns $[0,2,4,1]$. The heights first increase and then decrease, so all the water flows away over the left or the right edge. No column is completely under water, and the answer is $4$.

Clarification of the second example

The histogram is $[5,1,3,2,4,1]$. When Marko observes the whole histogram, the water between columns $1$ and $5$ stands up to height $4$, and to the right of column $5$ it all flows away. So $0,3,1,2,0,0$ units of water are held above the columns, $6$ in total. Columns $2$, $3$ and $4$ are completely under water and the remaining three are not, so the answer to the second question is $3$.

Scoring