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.

Input

Vào từ file văn bản TSEQ.INP:

• 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 \leq Q \leq 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 \leq X \leq 10^9; 1 \leq K \leq 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 \leq Y \leq 10^9; 1 \leq H \leq 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 \leq L \leq R \leq |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.

Output

Ghi ra file văn bản TSEQ.OUT:

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

Scoring

Sample Input 1

6
1 0 3
1 1 2
3 3 5
2 4 2
1 4 4
3 2 7

Sample Output 1

11
35

Notes