Little D is a master of data structures who particularly enjoys studying simple data structures. Today, he came up with the following problem:

You have a sequence $a$ of length $n$. You need to perform $q$ modifications or queries:

1. Given $v$, change all $a_i$ to $\min(a_i, v)$.
2. Change all $a_i$ to $a_i + i$.
3. Given $l, r$, query the sum $\sum_{i=l}^r a_i$.

The top-tier data structure master Little D solved this problem easily. Now, he intends to test you, as you are about to participate in IOI 2022, and he believes you can also solve this problem easily.

Input

The first line contains two positive integers $n$ and $q$, representing the length of the sequence and the number of modifications/queries, respectively.

The next line contains $n$ integers $a_i$, representing the initial sequence $a$.

The next $q$ lines each start with a positive integer $op_i$, representing the type of the $i$-th modification or query.

If $op_i = 1$, it is followed by an integer $v_i$, representing a type 1 modification.

If $op_i = 2$, it represents a type 2 modification.

If $op_i = 3$, it is followed by two positive integers $l_i, r_i$, representing a type 3 query.

Output

Several lines, each containing an integer representing the answer.

Examples

Input 1

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 1

33
9
107

Constraints

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

Property A: $a_i, v_i$ are generated randomly in $[0, 10^{12}]$, $op_i$ is generated randomly in $[1, 3]$, and $[l_i, r_i]$ is generated randomly from all valid intervals.