Cho một dãy số gồm n số nguyên và q truy vấn có dạng:

Loại ~1~ có dạng ~1~ ~k~ ~u~: Gán phần tử ở vị trí thứ ~k~ trong dãy số thành ~u~.

Loại ~2~ có dạng ~2~ ~a~ ~b~: In ra tổng các phần tử trong đoạn từ a đến b.

Input

• Dòng đầu tiên chứa hai số n và ~q~.
• Dòng thứ hai chứa n số nguyên.
• Mỗi dòng trong q dòng tiếp theo chứa 3 số nguyên thể hiện một truy vấn, có dạng ~1~ ~k~ ~u~ hoặc ~2~ ~a~ ~b~.

Output

Mỗi dòng là kết quả truy vấn loại 2.

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

(Nguồn: CSES)