Cho mảng \(A\) gồm \(N\) số nguyên. Hãy thực hiện hai loại truy vấn sau trên mảng:

• 1 pos val: Thay đổi giá trị tại vị trí \(pos\) thành \(val\) (\(A[pos] = val\)).
• 2 l r: Tính tổng các phần tử trong khoảng từ chỉ số \(l\) đến chỉ số \(r\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng 1 pos val (\(1 \le pos \le N\)) hoặc 2 l r (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra tổng các phần tử trên một dòng riêng biệt.

Ví dụ

Input:

5 3
1 2 3 4 5
2 1 3
1 3 10
2 2 4

Output:

6
16

Ràng buộc

• 30% số điểm ứng với \(N, Q \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.