Tổng Đoạn Động

Cho một mảng số nguyên $a$ gồm $n$ phần tử, đánh số từ $1$ đến $n$. Hãy xử lý $q$ thao tác theo đúng thứ tự:

• $1$ $k$ $u$: gán giá trị mới $a_k=u$;
• $2$ $l$ $r$: tính tổng $a_l+a_{l+1}+\cdots +a_r$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\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ủa đoạn được hỏi trên một dòng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le a_i,u\le 10^9$.
• $1\le k\le n$.
• $1\le l\le r\le n$.
• Mọi tổng đều nằm trong miền của số nguyên có dấu $64$-bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

8
12
28
3