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