== include(page="template/taskheader" task_id="expectedgoals") ==

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!

Poveste şi cerinţă...

h2. Date de intrare

The first line of the input file $expectedgoals.in$ contains $q$, the number of queries $1 ≤ q ≤ 10^6$.
 
The next $q$ lines of the input contain two integers $type$ and $k$ $1 ≤ type ≤ 2$, $1 ≤ k ≤ 10^6$, $1 ≤ p ≤ 10^6$; 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.

Fişierul de intrare $expectedgoals.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $expectedgoals.out$ ...

h2. Restricţii

* For tests worth $30$ points, $1 ≤ q ≤ 2 * 10^3$, $1 ≤ k ≤ 100$.
* For tests worth $30$ more points, $1 ≤ k ≤ 100$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. expectedgoals.in |_. expectedgoals.out |

| 10
1 20
1 8
1 14
1 11
2 3
1 5
1 8
1 11
2 5
2 7
| 33
43
77

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

After the first $5$ queries, the array is $20, 8, 14, 11$. The smallest amount of $xG$ we can get from $5$ 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$.

...

== include(page="template/taskfooter" task_id="expectedgoals") ==