Rikka with Bubble Sort

Problem Description

Bubble sort is a simple but beautiful algorithm. And this problem is a simple data structure task which is relative to bubble sort. Rikka has an integer array $A$ of length $n$, and then she makes $m$ operations on it. There are two types of operations:

1. 1 L R, Rikka runs the following C program on $A$. for (int i=L;i<R;i++) if (A[i]>A[i+1]) swap(A[i], A[i+1]);
2. 2 L R, Rikka wants to know the interval sum of $[L,R]$, i.e., $\sum_{i=L}^R A_i$.

Input

The first line contains two integers $n,m(1 \leq n \leq 10^6, 1 \leq m \leq 3 \times 10^4)$, and the second line contains $n$ integers $A_i(1 \leq A_i \leq 10^9)$. And then $m$ lines follow, each line contains three integers $t,L,R(t \in \{1,2\}, 1 \leq L \leq R \leq n)$.

Output

For each query, output a single line with a single integer, the answer.

Sample Input

5 6

1 5 4 5 1

1 3 5

2 2 4

1 2 4 

2 1 3

1 1 5

2 3 4

Sample Output

10

6

9

Source

2018 Multi-University Training Contest 9