Problem B
Racing Game

A certain game company famous for its PR stunts have just announced a new arcade racing game concept. Honestly, it is just like a standard racing game: players compete to finish each race in the fastest time, and they are ranked on a scoreboard based on their time. However, there is a twist: the company may sometimes increase or decrease all of the time records they have. "It is to motivate new players to try our game", they said.

As a game developer for that company, you are ordered to take care of the scoreboard system. Formally, you need to handle three types of operations:

• Put a new time record $X$ into the scoreboard.

• Add $Y$ to all existing time records on the scoreboard. Note that this might make some time records to be negative.

• Find the $Z$-th fastest time record on the scoreboard. Due to performance concerns, $Z$ is at most $10$.

Now, you have to run your program on $Q$ successive operations your colleague has prepared to test your program.

Input

The first line contains one integer $Q$ ($1\le Q\le 200000$), denoting the number of operations.

The next $Q$ lines will be in the form of one of the following:

• $1X$ ($0\le X\le 100000000$), meaning we have to put an integer $X$ to the scoreboard.

• $2Y$ ($-10000\le Y\le 10000$), meaning we have to add an integer $Y$ to all existing time records.

• $3Z$ ($1\le Z\le 10$), meaning we have to output the $Z$-th fastest time record on the scoreboard. It is guaranteed that there are at least $Z$ time records on the scoreboard.

Output

For each "$3Z$" operation, output the $Z$-th fastest time record in the scoreboard.

Subtasks

1. ($12$ Points): $Q\le 2000$, and $Z=1$ for each "$3Z$" operation.

2. ($13$ Points): $Q\le 2000$.

3. ($17$ Points): There is no "$2Y$" operation, and $Z=1$ for each "$3Z$" operation.

4. ($18$ Points): There is no "$2Y$" operation.

5. ($15$ Points): $Z=1$ for each "$3Z$" operation.

6. ($25$ Points): No additional constraints.

Explanation

In the first sample, below is what happened on each operation:

1. We put $11$ to the scoreboard. Hence, the scoreboard now contains $[11]$.

2. We have to output the $1$st fastest time record, which is $11$.

3. We add $29$ to all time records. Thus, the scoreboard becomes $[40]$.

4. We have to output the $1$st fastest time record, which is $40$.

5. We put $97$ to the scoreboard. Hence, the scoreboard now contains $[40,97]$.

6. We have to output the $2$nd fastest time record, which is $97$.

7. We put $0$ to the scoreboard. Hence, the scoreboard now contains $[40,97,0]$.

8. We add $-10$ to all time records. Thus, the scoreboard becomes $[30,87,-10]$.

9. We have to output the $2$nd fastest time record, which is $30$.

Warning

The I/O files are large. Please use fast I/O methods.

9
1 11
3 1
2 29
3 1
1 97
3 2
1 0
2 -10
3 2

11
40
97
30

11
1 1
2 -101
1 50
1 0
2 32
1 32
2 -1
3 1
3 2
3 3
3 4

-69
31
31
81