Nhập vào một mảng chứa \(n\) số nguyên. Cần trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

1. Thay đổi giá trị ở vị trí \(p\) thành \(v\);
2. In ra tổng của các số trong đoạn \([l,\ r]\).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(q\): lần lượt là kích thước của mảng và số lượng truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên \(x_1,\ x_2,\ldots,\ x_n\): giá trị của các phần tử trong mảng;
• Cuối cùng là \(q\) dòng mô tả \(q\) truy vấn. Mỗi truy vấn có dạng "\(1\ p\ v\)" hoặc "\(2\ a\ b\)".

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả trên một dòng.

Ràng buộc

• \(1\leq n,\ q\leq2\times10^5\);
• \(1\leq x_i,\ v\leq10^9\);
• \(1\leq p\leq n\);
• \(1\leq l\leq r\leq n\).

Ví dụ

Sample input

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

Sample output

14
2
11