Problem Description
Snuke is running a stall and there's a queue in front of him. However, sometimes people will leave the queue for no good reason, and they may also rejoin the queue at a later time. There are a total of Q events of these 3 types:
- Person x joins the queue, it is guaranteed that x is not in the queue.
- Person y leaves the queue, it is guaranteed that y is in the queue. y can be at any position in the queue
- The person at the front of the queue is served. The front person leaves the queue. It is guaranteed the queue is not empty when this query is called
Input
The first line of input will contain one integer Q. The next Q lines of input represent an event.
If the first number in that line is 1, someone is joining the line. The next number, Pi, is the number of the person joining the back of the queue.
If the first number in that line is 2, someone is leaving the queue. The next number, Pi, is the number of the person leaving the queue
If the first number in that line is 3, the front person is served
Output
For every type 3 query (someone is served), output the number of the person that is served, seperated by spaces.
Limits
For all subtasks: 1 ≤ Q ≤ 200 000, 1 ≤ Pi ≤ 109.
Subtask 1 (30%): Pi ≤ 200 000.
Subtask 2 (40%): It is guaranteed that someone who has left will not return to the queue
Subtask 3 (30%): No additional constraints.
Subtask 4 (0%): Sample testcases.
Sample Input
10
1 1
1 2
1 3
1 4
3
2 3
3
1 3
3
3
Sample Output
1 2 4 3