Siêu máy tính

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,\dots ,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ác phần tử được chèn ở thao tác loại $3$ có thể có giá trị nằm ngoài đoạn $[-{10}^9,{10}^9]$. Nếu dãy $S$ không có phần tử nào có giá trị trong đoạn $[a_i,b_i]$ thì tổng ở thao tác loại $2$ bằng $0$.

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.

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 ra câu trả lời tương ứng.

Dữ liệu vào

• 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$ theo khuôn dạng: bắt đầu là 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|$).

Dữ liệu ra

In 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. Dữ liệu đảm bảo có ít nhất một thao tác loại $2$ hoặc $3$.

Ràng buộc

• $1\le t\le {10}^5$;
• $-{10}^9\le x_i\le {10}^9$; $-{10}^9\le a_i\le b_i\le {10}^9$; $1\le p_i\le q_i\le |S|$.

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$.

Ví dụ