Tổng Đoạn Linh Hoạt

Cho một dãy gồm $n$ số nguyên. Bạn cần xử lý các phép gán giá trị mới cho một phần tử và các truy vấn tính tổng trên một đoạn liên tiếp. Mọi chỉ số trong đề đều được đánh số từ $1$.

Các thao tác có ý nghĩa như sau:

• $1$ $p$ $x$: gán $a_p=x$.
• $2$ $l$ $r$: in $a_l+a_{l+1}+\cdots +a_r$.

Input

• Dòng đầu chứa hai số nguyên $n,q$. Dòng thứ hai chứa $n$ số nguyên $a_1,\dots ,a_n$. Mỗi trong $q$ dòng tiếp theo mô tả một thao tác theo một trong hai dạng trên.

Output

• Với mỗi thao tác loại $2$, in tổng các phần tử từ $l$ đến $r$, kể cả hai đầu mút.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le a_i,x\le 10^9$.
• $1\le p\le n$ và $1\le l\le r\le n$.

Scoring

• Subtask $1$ ($50$ điểm): $n,q\le 2000$.
• Subtask $2$ ($50$ điểm): không có ràng buộc bổ sung.

Example

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

13
13
10