Note

The time limit for this problem is $1$ second.

Problem Statement

You are given a sequence $A$ of length $N$. Process $Q$ queries on it. There are two types of queries.

• Type $1$: Remove $A_l,A_{l+1},\dots,A_r$ from the sequence, and insert at that position the value $\displaystyle \sum_{i=l}^{r}A_i$ computed on the sequence before the removal (at this point, the indices of $A$ are reassigned in ascending order).
• Type $2$: Output the value of $\displaystyle \sum_{i=l}^{r}A_i$ at that moment.

Input

$N\ Q$
$A_1\ A_2\ \dots\ A_N$
$T_1\ l_1\ r_1$
$T_2\ l_2\ r_2$
$\vdots$
$T_Q\ l_Q\ r_Q$

• All input values are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $|A_i| \le 10^9$
• $1 \le T_i \le 2$
• $1 \le l_i \le r_i \le N_i$, where $N_i$ is the length of $A$ immediately before the $i$-th query.
• Each test case contains at least $1$ query of type $2$.

Output

For each query of type $2$, output the value of $\displaystyle \sum_{i=l}^{r}A_i$ at that moment, separated by newlines, and print a newline at the end.

Sample

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

36
27
3

16 9
-4 -2 -4 -1 -3 -3 7 7 5 -1 -1 6 5 10 -2 3
2 8 13
2 9 9
1 16 16
1 3 8
2 7 7
1 7 8
2 6 10
1 8 10
1 2 6

21
5
6
21