Old Is Not Gold

0

0 votes
Medium, Stack
Problem

A gold mine has asked for your help. Gold mine has two types of queries for you. Query type 1 - A gold coin of w gram is created by gold mine. Query type 2 - A customer has asked for x grams of gold. Now, the gold mine doesn't believe in "Old is gold" and hence will provide the customer the freshest gold coins even though if the customer gets more than x grams of gold.

Note that you need to give an entire gold coin to customer and hence the customer may get more than x grams of gold. However, if it is not possible to provide the customer x or more than x grams of gold, then the gold mine will not give any gold to the customer. Given q queries, for each query of type 2 print how much gold will be given to the customer. Note that once a gold coin is given to customer it cannot be further given to another customer.

See sample case for better understanding

 

Input format:

First line contains one integer q, denoting the number of queries.

Next q lines contains the queries.

Query of type 1 will be : 1 w

Query of type 2 will be : 2 x

Output format:

For each query of type 2, print the amount of gold(in gms) given to the customer.

 

Constraints:

1 <= q <= 200000(2e5)

1 <= w <= 10000(1e4)

1 <= x <= 1000000000(1e9)

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In query 1, 2 and 3,  3 new coins were made.

In query 4, a request of 4 gm gold is made, which is fulfilled by providing the freshest coins available(i.e. the 3 gram coin and the 2 gram coin) and so answer is 5. 

In query 5, a request of 2 gm gold is made, however as only 1 gm gold is available we will give 0 gm gold to customer.

In query 7, a request of 2 gm gold is made, which is fulfilled by providing the freshly made 2 gm gold coin.

Editor Image

?