Bạn được cho một mảng gồm n số nguyên. Nhiệm vụ của bạn là xử lý q truy vấn thuộc hai loại sau:

Cập nhật: thay đổi giá trị tại vị trí k thành u

Truy vấn: tính tổng các phần tử trong đoạn chỉ số từ a đến b

Đầu vào:

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~:

~n~: số lượng phần tử trong mảng

~q~: số lượng truy vấn

Dòng thứ hai chứa n số nguyên ~x_1~, ~x_2~, ..., ~x_n~: các giá trị ban đầu trong mảng.

Mỗi dòng trong q dòng tiếp theo mô tả một truy vấn. Mỗi truy vấn có dạng:

"1 k u": gán x[k] = u (cập nhật phần tử ở vị trí k thành u)

"2 a b": in ra tổng các phần tử từ x[a] đến x[b] (bao gồm cả hai đầu)

Đầu ra:

Với mỗi truy vấn loại 2, in ra tổng tương ứng trên một dòng.

🔒 Ràng buộc:

~1 \le n,q \le 2 \cdot 10^5~

~1 \le x_i, u \le 10^9~

~1 \le k \le n~

~1 \le a \le b \le n~

Ví dụ :

Input:

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Output:

14
2
11