Segment tree 2

Bạn được cho một mảng gồm \(n\) số nguyên. Ban đầu tất cả các phần tử trong mảng đều bằng \(0\). Nhiệm vụ của bạn là xử lý \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• \(1 \;x \; y\) — Gán phần tử tại vị trí \(x\) thành \(y\)
• \(2 \;l \; r\) — In ra tổng các phần tử từ \(a_l\) đến \(a_r\)

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\))
• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn có dạng như mô tả ở trên.
• Với truy vấn loại 1: \(1 \le x \le n\), \(|y| \le 10^9\)
• Với truy vấn loại 2: \(1 \le l \le r \le n\)

Output

• Với mỗi truy vấn loại 2, in ra tổng đoạn \([l, r]\) trên một dòng.

Scoring

• Subtask 1 (50%): \(n, q \le 1000\)
• Subtask 2 (50%): Không có ràng buộc thêm

Sample Input 1

5 5
2 1 5
1 3 10
2 1 5
1 5 -5
2 3 5

Sample Output 1

0
10
5