Bạn được cho một mảng \(a\) gồm \(n\) phần tử và \(q\) truy vấn. Có 2 loại truy vấn:

• Loại 1: có dạng \(1\) \(a\) \(b\) : Tăng phần tử thứ nhất trong đoạn [\(a, b\)] lên 1 đơn vị, phần tử thứ 2 lên 2 đơn vị, và cứ thế đến hết.
• Loại 2: có dạng \(2\) \(a\) \(b\) : Tính tổng tất cả các phần tử trong đoạn [\(a, b\)]

Input:

Dòng thứ nhất gồm 2 số \(n\) và \(q\)

Dòng thứ 2 gồm \(n\) phần tử của mảng \(a\)

\(q\) dòng còn lại, mỗi dòng là 1 truy vấn thuộc loại 1 hoặc 2.

Output:

Với mỗi truy vấn loại 2, in ra tổng của các phần tử trong đoạn [\(a, b\)]. Mỗi đáp án đều được in trên một dòng.

Constraints:

\(1\) ≤ \(n\), \(q\) ≤ \(2 .10 ^ 5\)

\(1\) ≤ \(a_i\) ≤ \(10^6\)

\(1\) ≤ \(a, b\) ≤ \(n\)

Example(s):

Input

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

Output

17
32