Xét một ống hình trụ nằm ngang. Bạn cần xử lý \(Q\) truy vấn thuộc một trong hai dạng:

• 1 x c: Đẩy \(c\) quả bóng, trên mỗi quả có ghi một số nguyên \(x\), vào đầu bên phải của hàng đợi.
• 2 c: Rút ra c quả bóng ở đầu bên trái của hàng đợi và in ra tổng của chúng.

Ta có thể giả sử rằng thứ tự của các quả bóng trong hàng đợi sẽ không bao giờ thay đổi.

Input

• Dòng đầu chứa số nguyên dương \(Q\) \(\left(1\le Q\le 2\times 10^5\right)\).
• Mỗi dòng trong \(Q\) dòng tiếp theo có dạng 1 x c hoặc 2 c như mô tả trên đề \(\left(0\le x\le 10^9, 1\le c\le 10^9\right)\). Dữ liệu đảm bảo tại mỗi truy vấn 2 c, trong hàng đợi đang chứa ít nhất \(c\) quả bóng.

Output

• Với mỗi truy vấn 2 c, in ra một dòng là câu trả lời tương ứng.

Ví dụ

Sample input 01

4
1 2 3
2 2
1 3 4
2 3

Sample output 01

4
8

Sample input 02

2
1 1000000000 1000000000
2 1000000000

Sample output 02

1000000000000000000