Cho dãy ~x~ gồm ~n~ số nguyên, bạn cần thực hiện ~q~ truy vấn có một trong hai dạng sau:

• ~1\ k\ u~: Cập nhật giá trị ở vị trí ~k~ thành ~u~ (~1 \le k \le n, 1 \le u \le 10^9~).
• ~2\ a\ b~: In tổng các giá trị trong đoạn ~[a, b]~ (~1 \le a \le b \le n~).

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n~ và ~q~, lần lượt là số lượng phần tử và số lượng truy vấn (~1 \le n, q \le 2 \cdot 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên ~x_1, x_2, \dots, x_n~ là các giá trị của dãy số (~1 \le x_i \le 10^9~).
• ~q~ dòng tiếp theo mỗi dòng gồm ba số nguyên thể hiện các truy vấn loại ~1~ hoặc ~2~.

Output

Với mỗi truy vấn loại ~2~ in ra kết quả tương ứng.

Sample Input 1

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

Sample Output 1

14
2
11