Given a sequence $a$ and a sequence $b$ initialized to $0$, you need to perform the following three types of operations:

• 1 x y: Update $a_x$ to $y$.
• 2 l r: For all $i \in [l, r]$, add $\max_{j=l}^{i} a_j$ to $b_i$.
• 3 l r: Calculate $\sum_{i=l}^{r} b_i$.

Input

The first line contains two positive integers $n$ and $m$, representing the length of sequence $a$ and the number of operations, respectively.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the sequence $a$.

The next $m$ lines each start with an integer $op$, representing the operation type, followed by two integers representing the operation parameters.

Output

For each operation where $op = 3$, output a single line containing an integer representing the answer to the query.

Constraints

For $100\%$ of the data, it is guaranteed that $1 \le n, m \le 5 \times 10^5$, $1 \le l \le r \le n$, $1 \le x \le n$, and $1 \le a_i, y \le 10^9$.

Examples

Input 1

5 5
2 1 4 3 5
2 1 3
2 4 3
1 2 3
3 1 3
3 2 5

Output 1

8
6

Input 2

10 10
5 6 10 3 6 7 10 10 1 10 
2 2 4
1 10 7
3 2 8
2 4 5
1 8 2
3 2 2
2 8 9
2 1 2
1 2 10
3 2 3

Output 2

26
6
22