Problem Description

You have been appointed as the new queue manager of disneyland

Since there are few rides and many people, there are always long queues at disneyland

There will be v visitors arriving today

Every visitor has a priority pi and an id ni

Once a new visitor arrives in the queue, if they have a higher (strictly greater than) priority than everyone else in the queue, they will enter the queue from the front, otherwise, they enter from the back

Once in a while, a new visitor is served, so they leave the queue, when this happens, you need to output the id of that visitor so that people can know when to leave the queue

Note: 2 people can have the same priority, but not the same id

Input

The first line of the input contains one integer, the number of operations n

For the next n lines, each line consists of an integer, either 0 or 1, 1 indicating entry and 0 indicating service of a person. This integer is followed by two other integers, pi and ni, indicating the priority of the person and the id of the person if the first integer is 1, otherwise, there will not be any additional integers

Constraints

1<=v<=1,000,000

1<=ni<=1,000,000

1<=pi<=1,000,000,000

Output

For each serve operation (i.e. 0), output an integer on a line, the id of the person who will be served

If there are no people in the queue when during a serve operation, output -1 for that line [It is certainly possible to serve with no customers]

Subtasks

Subtask 1 (10%) n<=100

Subtask 2 (25%) n<=5000

Subtask 3 (65%) n<=1000000

Sample Testcase 1

Input

3
1 5 4
0
0
Output
4
-1

Explanation

Guy with id 4 is served, noone else is

Sample Testcase 2

Input

5
1 5 4
1 9 3
1 7 7
0
0
Output
3
4

Explanation

Guy with id 3 cuts queue to front, gets served first, guy with id 7 does not get to cut, cos guy with id 3 (priority 9) is in the queue, hence guy with id 4 goes second