Bình đang chơi một trò chơi xây dựng thành phố trên một vùng đất vô hạn. Vùng đất này có các ô đất được đánh số liên tiếp từ \(1\) đến \(10^9\). Ban đầu, tất cả các ô đất đều có giá trị tài nguyên bằng \(0\). Trong quá trình chơi, Bình thực hiện hai loại thao tác:

• 1 pos val: Bình xây dựng hoặc nâng cấp công trình tại ô đất có chỉ số \(pos\), khiến giá trị tài nguyên của ô đất này thay đổi thành \(val\).
• 2 l r: Bình muốn tính tổng giá trị tài nguyên của toàn bộ các ô đất nằm trong khoảng từ chỉ số \(l\) đến chỉ số \(r\).

Hãy viết chương trình giúp Bình thực hiện nhanh chóng các thao tác trên để tối ưu hóa việc quản lý tài nguyên.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(Q\) (\(1 \le Q \le 5 \cdot 10^4\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa thông tin của một thao tác theo một trong hai định dạng:
  • 1 pos val (\(1 \le pos \le 10^9, 1 \le val \le 10^9\)).
  • 2 l r (\(1 \le l \le r \le 10^9\)).

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra tổng tài nguyên tìm được trên một dòng riêng biệt.

Ví dụ

Input:

4
1 1000000000 5
1 500000 10
2 1000 1000000000
2 1 100000

Output:

15
0