注意

この問題の実行時間制限は $1$ 秒です。

問題文

長さ $N$ の数列 $A$ が与えられます。これに対する $Q$ 個のクエリを処理してください。与えられるクエリには以下の二種類があります。

• タイプ $1$ : $A_l,A_{l+1},\dots,A_r$ を数列から削除し、削除する前の数列における $\displaystyle \sum_{i=l}^{r}A_i$ をその位置に挿入する(このとき $A$ の添え字は改めて昇順に振り分けられる)。
• タイプ $2$ : その時点での $\displaystyle \sum_{i=l}^{r}A_i$ を出力する。

入力

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

• 入力は全て整数
• $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$
• $i$ 個目のクエリ直前の $A$ の長さを $N_i$ として $1 \le l_i \le r_i \le N_i$
• 各テストケースにタイプ $2$ のクエリは $1$ つ以上存在する

出力

タイプ $2$ の各クエリについて各時点での $\displaystyle \sum_{i=l}^{r}A_i$ を改行区切りで出力し、最後に改行してください。

サンプル

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