Công ty Long Vân giới thiệu siêu máy tính có khả năng thực hiện được tỉ tỉ phép toán trong vòng một giây. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện một số lượng rất lớn các thao tác như sau:

• Ban đầu, dãy ~S~ không có phần tử nào;
• Có ~t~ thao tác, thao tác thứ ~i~ (~i = 1, 2, ..., t~) thuộc một trong ba loại:
  1. Thêm vào dãy ~S~ một phần tử mới ~x_i~;
  2. Tính tổng các phần tử của dãy ~S~ hiện tại có giá trị nằm trong đoạn ~[a_i, b_i]~;
  3. Sắp xếp dãy ~S~ hiện tại theo thứ tự không giảm rồi tính tổng tất cả các phần tử có thứ tự từ ~p_i~ đến ~q_i~ (~1 \le p_i \le q_i \le |S|~, trong đó ~|S|~ là số lượng phần tử của dãy ~S~ hiện tại). Sau đó, chèn vào dãy ~S~ hai phần tử, một phần tử có giá trị bằng phần tử có thứ tự ~p_i~ cộng với 1 và phần tử có giá trị bằng phần tử có thứ tự ~q_i~ trừ đi 1.

Công ty sẽ trao thưởng cho người nào kiểm chứng được kết quả mà siêu máy tính đưa ra. Bạn được cho dãy gồm ~t~ thao tác, với mỗi thao tác loại 2 và 3 hãy đưa câu trả lời tương ứng.

Yêu cầu: Cho dãy gồm ~t~ thao tác, với mỗi thao tác loại 2 và 3 hãy đưa câu trả lời tương ứng.

Input

• Dòng đầu chứa số nguyên dương ~t~;
• Dòng thứ ~i~ trong ~t~ dòng tiếp theo mô tả thao tác thứ ~i~ là một trong ba loại thao tác theo khuôn dạng: Bắt đầu số ~k_i~ (~k_i~ bằng 1 hoặc 2 hoặc 3). Nếu là thao tác loại 1 thì tiếp theo là một số nguyên ~x_i~ (~-10^9 \le x_i \le 10^9~), nếu là thao tác loại 2 thì tiếp theo là hai số nguyên ~a_i, b_i~ (~-10^9 \le a_i \le b_i \le 10^9~), còn nếu là thao tác loại 3 thì tiếp theo là hai số nguyên dương ~p_i, q_i~ (~1 \le p_i \le q_i \le |S|~).

Output

• Ghi ra một số dòng, mỗi dòng chứa một số lần lượt là các câu trả lời cho các thao tác loại 2, 3 theo thứ tự xuất hiện ở dữ liệu vào.

Sample Input 1

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

Sample Output 1

3
5
10

Subtasks

• Có 40% số test ứng với 40% số điểm có ~t~ không vượt quá ~10^3~;
• Có 40% số test khác ứng với 40% số điểm có ~t~ không vượt quá ~10^5~ và không có thao tác loại 3;
• Có 20% số test còn lại ứng với 20% số điểm có ~t~ không vượt quá ~10^5~.