Tăng là một cậu bé rất thích học toán và chơi game. Một hôm, cậu được mẹ cho tham gia một trò chơi mô phỏng trên trục số. Ban đầu, tất cả các vị trí trên trục số đều có giá trị bằng ~0~. Tăng phải thực hiện một chuỗi ~Q~ thao tác thuộc hai dạng:

• Thao tác cập nhật: Cộng thêm giá trị ~p~ vào tọa độ ~i~ trên trục số nguyên không âm.
• Thao tác truy vấn: Tính tổng tất cả các giá trị hiện có trên đoạn ~[L, R]~.

Yêu cầu: Bạn hãy viết chương trình giúp Tăng xử lý toàn bộ ~Q~ truy vấn trên!

Input

• Dòng ~1~: Chứa số nguyên ~Q~ — số lượng truy vấn. ~(Q \le 10^5)~
• ~Q~ dòng tiếp theo, mỗi dòng biểu diễn một truy vấn thuộc một trong hai dạng:
  • 1 i p: Cập nhật cộng thêm ~p~ vào vị trí ~i~. ~(i, p \le 10^9)~
  • 2 L R: Tính tổng các giá trị trên đoạn ~[L, R]~. ~(1 \le L \le R \le 10^9)~

Output

• Với mỗi thao tác truy vấn, in ra trên một dòng một số nguyên duy nhất là tổng các giá trị nằm trên đoạn ~[L, R]~ tương ứng.

Example Input 1

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

Example Output 1

15
3

Example Input 2

3
1 1000000000 100
2 1 500000000
2 500000000 1000000000

Example Output 2

0
100

Example Input 3

4
1 5 10
2 1 4
2 5 5
2 1 10

Example Output 3

0
10
10