Cho một dãy gồm \(n\) số nguyên \(a_0\), \(a_1\), \(a_2\),..., \(a_{n-1}\), bạn hãy viết chương trình thực hiện \(q\) truy vấn thuộc một trong hai loại sau:

• 0 p x: Tăng giá trị \(a_p\) lên \(x\) đơn vị.
• 1 l r: Tính và in ra tổng \(a_l + a_{l+1} + ... + a_{r-2} + a_{r-1}\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) \(\left(1\le n, q\le 5\times 10^5\right)\).
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_0\), \(a_1\), \(a_2\),..., \(a_{n-1}\) (\(a_i \le 10^9\) với mọi \(i\)).
• \(q\) dòng tiếp theo, mỗi dòng có dạng \(0\) \(p\) \(x\) hoặc \(1\) \(l\) \(r\) như mô tả ở trên. Dữ liệu đảm bảo \(p\), \(x\), \(l\), \(r\) đều là số nguyên, đồng thời \(0\le p < n\), \(0\le x \le 10^9\), và \(0\le l < r\le n\).

Output

• Với mỗi truy vấn dạng 1 l r, in ra tổng cần tìm.

Ví dụ

Sample input 01

6 6
1 2 3 4 5 6
1 0 5
1 2 4
1 1 3
0 4 11
1 0 6
1 1 5

Sample output 01

15
7
5
32
25