Nhập vào một mảng chứa \(n\) số nguyên. Cần trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

1. Tăng giá trị phần tử đầu tiên trong đoạn \([l,\ r]\) lên \(1\) đơn vị, phần tử thứ \(2\) lên \(2\) đơn vị, phần tử thứ \(3\) lên \(3\) đơn vị, ...;
2. In ra tổng giá trị của tất cả phần tử trong đoạn \([l,\ r]\).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(q\): lần lượt là kích thước của mảng và số lượng truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên \(x_1,\ x_2,\ldots,\ x_n\): giá trị của các phần tử trong mảng;
• Cuối cùng là \(q\) dòng mô tả \(q\) truy vấn. Mỗi truy vấn có dạng "\(1\ l\ r\)" hoặc "\(2\ l\ r\)".

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả trên một dòng.

Ràng buộc

• \(1\leq n,\ q\leq2\times10^5\);
• \(1\leq x_i,\ v\leq10^6\);
• \(1\leq p\leq n\);
• \(1\leq l\leq r\leq n\).

Ví dụ

Sample input

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

Sample output

17
32