Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1,A_2..A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu

Thực hiện tất cả \(Q\) thao tác và in ra kết quả của thao tác loại \(2\).

Dữ liệu vào

• Dòng thứ nhất gồm hai số nguyên dương \(N,Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ... A_N\) \((A_i \le 10^9)\)
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \le p_i \le N, 1 \le x_i \le 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \le u_i \le v_i \le N)\)

Dữ liệu ra

• Với thao tác loại \(2\) có dạng \(2 u v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Ràng buộc

• Subtask 1 (50% số điểm): \(N \le 10^3, Q \le 10^3\)
• Subtask 2 (50% số điểm): \(N \le 10^5, Q \le 10^5\)

Input 1

6 5
9 2 4 7 4 8
1 5 6
2 1 5
1 3 8
1 2 3
2 2 4

Output 1

32
24