The day before Halloween, many shoppers attempt to buy candy last minute, causing candy stores to run out of candy. Luckily, one candy store is well prepared having ordered candies in advance to be delivered on this day.

Throughout the day, batches of candy are delivered to the store, with each candy having an associated sweetness value. Since the store remains open 24/7, shoppers also come to purchase candy while deliveries may be occurring. The shelves are stocked depending on the store's most recent delivery. This means that shoppers will only purchase the most recently delivered candies. If the store runs out of the most recently delivered candy, the shelves will be restocked with the the second most recently delivered candy, then the third, and fourth, and so on. This will continue until either the store runs out of all candy or the shopper purchases their desired amount of candy. If the store does not have enough candy to satisfy the customer, they will purchase all the remaining candy in the store before leaving.

Input Specification

The first line will contain one integers ~N~ ~(1 \le N \le 10^5)~, the number of people who stop by throughout the day. Each person visiting can be of two different types, a delivery person delivering ~V~ ~(1 \le V \le 10^4)~ amount of candy with a sweetness value of ~S~ ~(1 \le S \le 10^4)~, or a shopper who will purchase ~P~ ~(1 \le P \le 10^4)~ of the most recently delivered candies.

The next ~N~ lines begin with a single integer ~T~ representing the type of person visiting, where 1 represents a delivery person, and 2 represents a shopper. For each delivery person, two integers ~V~ and ~S~ will follow. For each shopper, a single integer ~P~ will follow.

Output Specifications

For each shopper, print out the sum of the sweetness values of every candy they purchased.

Subtasks

Subtask 1 [2/7]:

• ~N \le 10^3~
• ~P, V \le 10^2~

Subtask 2 [2/7]:

• ~P, V \le 10^3~

Subtask 3 [4/7]:

• No further constraints

Sample Input 1

5
1 1 1
2 1
1 1 1
1 1 2
2 2

Sample Output 1

1
3

Explanation for Sample Output 1

The first person delivers 1 candy of sweetness 1. The shelves now contain [1], one candy of sweetness 1.
The second person purchases 1 candy. The total sweetness of their purchase is now 1. The shelves are now empty.
The third person delivers 1 candy of sweetness 1. The shelves now contain [1], one candy of sweetness 1.
The fourth person delivers 1 candy of sweetness 2. The shelves now contain [2, 1], one candy of sweetness 2 and one candy of sweetness 1.
The last purchases 2 candy. In order, they first obtain 1 candy of sweetness 2 then 1 candy of sweetness 1. The shelves are now empty. The total sweetness of their purchase is 3.

Sample Input 2

10
2 10
1 1 1
1 2 2
2 1
1 1 3
1 6 2
2 8
2 10
1 10 4
2 1

Sample Output 2

0
2
17
1
4

Explanation for Sample Output 2

The following [] represents the stock of the shelves throughout the day:
Person 1: Purchases 0 candy emptying the shelves, total sweetness = 0, [].
Person 2: Delivers 1 candy of sweetness 1, [1].
Person 3: Delivers 2 candies of sweetness 2, [2, 2, 1].
Person 4: Purchases 1 candy, total sweetness = 2 [2, 1].
Person 5: Delivers 1 candy of sweetness 3, [3, 2, 1]).
Person 6: Delivers 6 candies of sweetness 2, [2, 2, 2, 2, 2, 2, 3, 2, 1].
Person 7: Purchases 8 candies, total sweetness = 17, [1].
Person 8: Purchases 1 candy emptying the shelves, total sweetness = 1, [].
Person 9: Delivers 10 candies of sweetness 4, [4, 4, 4, 4, 4, 4, 4, 4, 4, 4].
Person 10: Purchases 1 candy, total sweetness = 4, [4, 4, 4, 4, 4, 4, 4, 4, 4].