Bạn được cho một mảng gồm ~n~ số nguyên. Ban đầu tất cả các số của mảng đều là 0. Nhiệm vụ của bạn là xử lí 2 loại truy vấn:

• Loại 1 có dạng ~1~ ~x~ ~y~: Gán phần tử ở vị trí thứ ~x~ trong dãy thành số ~y~ (~1\le x\le n,|y|\le 10^9~)
• Loại 2 có dạng ~2~ ~l~ ~r~: In ra tổng các phần tử trong đoạn từ ~l~ đến ~r~ (~1\le l\le r\le n~)

Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input

• Dòng đầu tiên là hai số ~n~ và ~q~ lần lượt là số phần tử của mảng (~1\le n\le 10^5~) và số truy vấn (~1 \le q \le 10^5~).
• ~q~ dòng sau, mỗi dòng là một truy vấn thuộc một trong 2 loại trên.

Output

Với mỗi truy vấn loại 2, in ra câu trả lời trên một dòng

Sample Input

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

Sample Output

7
11
10