Goal Statistics

Lately, Stefan has been interested in studying football statistics and one day, he discovered a new metric called "expected goals" $xG$. In order to see how can $xG$ affect football games, he gathered data from various football games and now he needs your help to process the data he got.

In order to start the research, he told you that there will be $q$ events during the football season, and the events are of two types:

$1 \ k$: His database gets a scoring chance worth $k \ xG$. Since $xG$ is usually represented as a real number, he gave you its value multiplied by $10^6$, so that $k$ is an integer. Therefore, $k$ can be between $1$ and $10^6$, on a probability scale from $10^{-6}$ to $1$ (the probability can never be equal to $0$).

$2 \ p$: He wants to find the smallest amount of $xG$ needed in order for a team to score $p$ goals, if we assume that all the scoring chances have been converted into goals.

The database became really big and Stefan got into trouble, so it's up to you to help him!

Input data

The first line of the input contains $q$, the number of queries.

The next $q$ lines of the input contain two integers $type$ and $k$. For type $2$, $p$ is guaranteed to be at most equal to the number of events of type $1$ which happened already before the current query.

Output data

The output will contain on each line, the answers for the queries of type $2$, in the order from the input.

Constraints and Clarifications

• $1 \leq type \leq 2$;
• $1 \leq q \leq 10^6$;
• $1 \leq k \leq 10^6$;
• $1 \leq p \leq 10^6$;
• For tests worth $30$ points, $1 \leq q \leq 2 \cdot 10^3$, $1 \leq k \leq 100$.
• For tests worth $30$ more points, $1 \leq k \leq 100$.

Example 1

stdin

10
1 20
1 8
1 14
1 11
2 3
1 5
1 8
1 11
2 5
2 7

stdout

33
43
77

Explanation

After the first $5$ queries, the array is $20$, $8$, $14$, $11$. The smallest amount of $xG$ we can get from $3$ values is obtained by taking $8$, $11$ and $14$ and the $xG$ sum is $33$.

After the first $9$ queries, the array is $20$, $8$, $14$, $11$, $5$, $8$, $11$. The smallest amount of $xG$ we can get from $5$ values is obtained by taking $8$, $11$, $5$, $8$ and $11$ and the $xG$ sum is $43$.

After the first $10$ queries, the array is $20$, $8$, $14$, $11$, $5$, $8$, $11$ and we have to take every single value, and the sum is $77$.