B. Mua kẹo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bảo sở hữu một cái máy bán kẹo, nguyên lý hoạt động của máy này là kẹo sẽ được trữ bên trong một đường ống, khi nhấn nút để mua kẹo, thì kẹo ở cuối đường ống sẽ được nhả ra.

Trong một ngày Bảo có $$$q$$$ sự kiện diễn ra bao gồm hai loại sau:

  • $$$1$$$ $$$x$$$ $$$a$$$: Bảo nạp $$$x$$$ viên kẹo loại $$$a$$$, có giá $$$a$$$/viên vào đầu đường ống của máy bán kẹo
  • $$$2$$$ $$$c$$$: Khách hàng mua $$$c$$$ viên kẹo.

Hãy cho biết mỗi lần mua kẹo, khách hàng sẽ phải trả bao nhiêu tiền.

Dữ liệu vào luôn bảo đảm có đủ kẹo cho mỗi lần khách mua và sẽ có ít nhất một lần khách mua kẹo.

Input

Dòng đầu tiên gồm một số nguyên duy nhất $$$t$$$ ($$$1 \le t \le 10^4$$$) $$$-$$$ số testcases

Dòng đầu tiên của mỗi testcase gồm một số nguyên duy nhất $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) $$$-$$$ số sự kiện trong ngày.

$$$q$$$ dòng tiếp theo của mỗi testcase thuộc một trong hai dạng sau:

  • $$$1$$$ $$$x$$$ $$$a$$$ ($$$1 \le x, a \le 10^9$$$) $$$-$$$ Bảo nạp $$$x$$$ viên kẹo loại $$$a$$$ vào đầu đường ống của máy bán kẹo
  • $$$2$$$ $$$c$$$ ($$$1 \le c \le 10^9$$$) $$$-$$$ Khách hàng mua $$$c$$$ viên kẹo.

Dữ liệu vào bảo đảm tổng $$$q$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$.

Output

Ở mỗi testcase, gọi $$$k$$$ là số sự kiện loại $$$2$$$ $$$c$$$. Trên $$$k$$$ dòng hãy in số tiền cần để mua kẹo.

Example
Input
1
5
1 2 3
2 1
1 4 5
2 3
2 2
Output
3
13
10
Note

Ở ví dụ đầu tiên:

Sau sự kiện thứ nhất, đường ống như sau:

đầu [$$$3, 3$$$] cuối

Sau sự kiện thứ hai, số tiền mua kẹo là $$$1 \times 3 = 3$$$. Lúc này đường ống như sau:

đầu [$$$3$$$] cuối

Sau sự kiện thứ ba, đường ống như sau:

đầu [$$$5, 5, 5, 5, 3$$$] cuối

Sau sự kiện thứ tư, số tiền mua kẹo là $$$1 \times 3 + 2 \times 5 = 13$$$. Lúc này đường ống như sau:

đầu [$$$5, 5$$$] cuối

Sau sự kiện thứ năm, số tiền mua kẹo là $$$2 \times 5 = 10$$$. Lúc này đường ống như sau:

đầu [] cuối