Hai dãy số

Với niềm đam mê về các bài toán trên dãy số của mình, hôm nay thầy giáo Lê nghiên cứu bài toán trên hai dãy số $A$ và $B$.

Dãy $A$ gồm các số tự nhiên sắp xếp tăng dần từ $1$ tới ${10}^9$. Dãy $B$ chỉ gồm duy nhất một số $0$. Thầy Lê lần lượt đưa ra $Q$ yêu cầu, mỗi yêu cầu thuộc một trong $3$ loại sau:

• Loại 1: Cho hai số $X$ và $K$, yêu cầu cắt $K$ số đầu tiên của dãy $A$, ghép vào ngay sau số có giá trị $X$ của dãy $B$;
• Loại 2: Cho hai số $Y$ và $H$, yêu cầu xóa đi $H$ số ngay sau số có giá trị $Y$ của dãy $B$;
• Loại 3: Cho hai số $L$ và $R$, yêu cầu tính tổng của các số từ vị trí $L$ đến vị trí $R$ của dãy $B$. Vị trí các phần tử trong dãy $B$ được đánh số từ $1$.

Yêu cầu: Hãy thực hiện các yêu cầu đó theo đúng thứ tự mà thầy Lê đưa ra.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $Q$ là số lượng yêu cầu thầy Lê cần thực hiện $(1\le Q\le 5\times {10}^5)$.
• Mỗi dòng trong số $Q$ dòng tiếp theo chứa ba số nguyên mô tả một trong ba loại yêu cầu theo định dạng sau:
  • Loại 1: 1 $X$ $K$ mô tả yêu cầu loại 1 $(0\le X\le {10}^9;1\le K\le {10}^9)$. Dữ liệu bảo đảm tổng $K$ của tất cả các yêu cầu loại 1 không quá ${10}^9$ và giá trị $X$ hiện đang có trong dãy $B$;
  • Loại 2: 2 $Y$ $H$ mô tả yêu cầu loại 2 $(0\le Y\le {10}^9;1\le H\le {10}^9)$. Dữ liệu bảo đảm có ít nhất $H$ số sau giá trị $Y$ và giá trị $Y$ hiện đang có trong dãy $B$;
  • Loại 3: 3 $L$ $R$ mô tả yêu cầu loại 3 $(1\le L\le R\le |B|)$, với $|B|$ là số lượng phần tử hiện tại của dãy $B$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Với mỗi yêu cầu loại 3, in ra trên một dòng một số nguyên là đáp án tính được.

Ràng buộc

• $1\le Q\le 5\times {10}^5$.
• Loại 1: $0\le X\le {10}^9$, $1\le K\le {10}^9$; tổng $K$ của tất cả các yêu cầu loại 1 không quá ${10}^9$; $X$ hiện đang có trong dãy $B$.
• Loại 2: $0\le Y\le {10}^9$, $1\le H\le {10}^9$; $Y$ hiện đang có trong dãy $B$ và có ít nhất $H$ số sau $Y$.
• Loại 3: $1\le L\le R\le |B|$.

Subtasks

• Subtask 1 ($15\%$ số điểm): $Q,K\le 500$.
• Subtask 2 ($15\%$ số điểm): $Q\le 5000$.
• Subtask 3 ($20\%$ số điểm): Không có yêu cầu loại $2$; các yêu cầu loại $1$ xuất hiện trước tất cả các yêu cầu loại $3$.
• Subtask 4 ($25\%$ số điểm): Không có yêu cầu loại $2$.
• Subtask 5 ($25\%$ số điểm): Không có ràng buộc nào thêm.

Ví dụ