Fences and Peak Blocks

Time limit: 2000 msMemory limit: 250 MB

You are given an array of $N$ integers and $N-1$ toggleable fences placed between consecutive positions. The fence with index $p$ lies between positions $p$ and $p+1$ for $1 \le p < N$ . All fences start inactive (down).

For any interval $[L, R]$ , define its blocks as the maximal contiguous subsegments obtained by cutting at every fence whose index $j$ satisfies $L \le j < R$ . The score of $[L, R]$ is the sum, over all its blocks, of the maximum value within each block. Formally, if the blocks are with , then the score is

Process $Q$ operations of the following types:

Type 1: set $A_i = x$ .
Type 2: toggle the fence between positions $p$ and $p+1$ (from down to up, or from up to down).
Type 3: given $L$ and , report the score of .

Indices are $1$ -based. When $L = R$ , the score equals $A_L$ regardless of fences.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N \le 2 \times 10^5$ , ), the number of positions and the number of operations. The second line contains integers (). Each of the next lines describes one operation in one of the following formats (all indices are -based):

Output

For each operation of type 3, print a single line with one integer: the score of the queried interval $[L, R]$ . No output is produced for operations of type 1 or type 2.

Samples

Sample 1

Input

Output

Initially, all fences are down. Query over $[1,5]$ uses one block with maximum $5$ . After toggling the fence at $p=2$ , $[1,5]$ splits into and with maxima and , summing to . Toggling the fence at and querying yields blocks , , with maxima , , and . After setting , the same query sums to . Finally, toggling again leaves only the fence at , so becomes two blocks with maxima and .

Fences and Peak Blocks

Input

Output

Samples

Sample 1

Submit

Submissions