chmin

Task

You are given an array $a$ of length $N$ on which you need to perform $Q$ operations. These come in two types, encoded as follows:

• 0 st dr x: $a[i] = \min(a[i], x)$ for $st \leq i \leq dr$;
• 1 st dr: print $\sum\limits_{i=st}^{dr} a[i]$.

Input data

On the first line, the numbers $N$ and $Q$ are given. On the second line, the array $a$ (indexed from $1$) is given. On the next $Q$ lines, there is one operation per line.

Output data

The results of the type 1 operations, each on a separate line.

Constraints and clarifications

• $1 \leq N, Q \leq 2\cdot10^{5}$
• $0 \leq a[i], x \leq 10^9$
• $1 \leq st \leq dr \leq N$
• It is recommended to use the following line of code at the beginning of the main function, it will decrease the input reading time: cin.tie(0)->sync_with_stdio(0);.

Example

stdin

3 2
1 2 3
0 1 3 1
1 1 3

stdout

3

Explanation

After the first operation, the array becomes $[1, 1, 1]$. The sum of the indices from $1$ to $3$ is $3$.