Hugo stores his lego inside a bag. He can perform four types of operations:

1. Store a piece of lego of size $x$ $(1 \le x \le 10^6)$ into the bag.
2. Take out a piece of lego of size $x$ from the bag. It is guaranteed such a piece of lego will exist.
3. Query the $k$'th largest piece of lego in the bag, where $1 \le k \le 10$. If there are less than $k$ pieces of lego in the bag, you should answer $-1$.
4. Query the $k$'th smallest piece of lego in the bag, where $1 \le k \le 10$. If there are less than $k$ pieces of lego in the bag, you should answer $-1$.

Input

The first line of input consists of an integer $N$, the number of operations.
Each of the next $N$ lines are of the form q x (operation type 1 or 2) or q k (operation type 3 or 4).

Output

For each operation of type 3 or 4, output an integer on its own line to answer Hugo's query.

Constraints

Subtask 1 (30%): $1 \le N \le 3000$
Subtask 2 (70%): $1 \le N \le 5 \times 10^5$