Description

There are several NTHU students lining up for shu cream.

Each student belongs to a group identified by an integer g. When a student joins the queue:

• If there is already someone from the same group g in the queue, this student will insert right behind the last student of group g.
• Otherwise, the student simply joins at the end of the queue.

Occasionally, the staff scolds an entire group for being too loud. When this happens, all students of that group must move together to the end of the queue, while keeping their relative order unchanged.

Now, you are required to write a program to simulate the queue. There are four type of events:

• JOIN id g: A student of student ID id and group g want to joint the queue.
• SCHOLD g: The staff scolds the students in group g.
• LEAVE: The first student in the queue gets his/her shu cream and leave the queue.
• ASK pos: Your program should answer what is the student ID of the student that is in the pos-th position of queue (1-base).

Your program MAY use C++ standard library headers.

Input

The first line contains a number N, representing the number of events.

For the next N lines, each line contains an event.

• 1 <= N <= 5 * 10^4
• 1 <= g <= 2000
• Each group have at most 1000 students.
• id <= 2 * 10^6
• pos is always less than or equal to the length of queue.
• There is at least one student of group g whenever the event SCOLD g happens.

Output

The student IDs, one per line. Each line should be newline ('\n') terminated.

Sample Input  Download

Sample Output  Download

Tags

Discuss