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

Constraints

• \(1 \leq n, q \leq 2\cdot 10^5\)
• \(1 \leq a_i \leq 10^6\)
• \(1 \leq a, b \leq n\)

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

Example

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

17
32