# #712. 【北大集训2021】简单数据结构

1. 给定 $v$，将所有 $a_i$ 变为 $\min(a_i, v)$。

2. 将所有 $a_i$ 变为 $a_i + i$。

3. 给定 $l, r$，询问 $\sum_{i=l}^r a_i$。

### 样例

#### input

15 15
6 14 14 6 3 6 4 13 10 3 12 5 11 9 6
1 9
1 2
2
2
2
1 11
3 4 6
2
1 6
2
1 9
1 11
1 11
3 4 4
3 2 13



#### output

33
9
107



### 数据范围与提示

$1$ $10$ $5000$
$2$ $20$ $200000$ A
$3$ $15$ $200000$ $op_i\neq 2$
$4$ $55$ $200000$

$1 \leq n, q \leq 2 \times 10^5, 0 \leq a_i, v_i \leq 10^{12}$