Cho một dãy số \(S\) ban đầu rỗng. Thực hiện \(t\) thao tác, mỗi thao tác thuộc một trong ba loại sau:

1. Thêm phần tử \(x\) vào cuối dãy \(S\).
2. Tính tổng các phần tử trong \(S\) có giá trị nằm trong đoạn \([a, b]\).
3. Sắp xếp \(S\) theo thứ tự không giảm, sau đó:
   • Tính tổng các phần tử có vị trí từ \(p\) đến \(q\) trong dãy đã sắp xếp.
   • Thêm vào cuối \(S\) hai phần tử:
     • Một có giá trị là phần tử thứ \(p\) cộng thêm 1
     • Một có giá trị là phần tử thứ \(q\) trừ đi 1

Dữ liệu vào

• Dòng đầu tiên: Số nguyên \(t\) — số thao tác.
• \(t\) dòng tiếp theo: Mỗi dòng mô tả một thao tác theo định dạng:
  • \(1\) \(x\) — thao tác loại 1: thêm phần tử \(x\) vào cuối \(S\).
  • \(2\) \(a\) \(b\) — thao tác loại 2: tính tổng các phần tử trong đoạn giá trị \([a, b]\).
  • \(3\) \(p\) \(q\) — thao tác loại 3:
    • sắp xếp \(S\) không giảm,
    • tính tổng các phần tử có thứ tự từ \(p\) đến \(q\) (1-based),
    • thêm hai phần tử mới như mô tả trên.

Dữ liệu ra

• Với mỗi thao tác loại 2 và loại 3, in ra kết quả tính tổng tương ứng, mỗi kết quả trên một dòng.

Ràng buộc

• 40% số test: \(t ≤ 1000\)
• 40% số test: \(t ≤ 10^5\), không có thao tác loại 3
• 20% số test: \(t ≤ 10^5\)

Input 1

7
1 5
1 3
1 1
2 2 4
1 2
3 2 3
2 2 4

Output 1

3
5
10