Bạn được cho một mảng gồm ~n~ phần tử. Ban đầu tất cả các phần tử đều bằng ~0~. Có ~q~ truy vấn cần được bạn giải quyết.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ , ~q~ - số lượng phần tử của mảng và số lượng truy vấn.
• Tiếp theo là ~q~ dòng mỗi dòng có thể thuộc hai dạng:
  • Dạng ~1~ ~k~ ~v~ : Tăng giá trị của phần tử thứ ~k~ thêm ~v~ đơn vị.
  • Dạng ~2~ ~pos~ : In ra giá trị tại vị trí ~pos~.

Output

• In ra kết quả đối với mỗi truy vấn loại ~2~.

Constraints

• ~1 \le n \le 10^{9}~.
• ~1 \le q \le 2 \times 10^5~.
• ~1 \le k,pos \le n~.
• ~1 \le v \le 10^9~.

Sample Input 1

5 3
1 4 3
1 4 8
2 4

Sample Output 1

11