Time limit: 5s
Memory limit: 256MB
Input:
Output:

## 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$.