Description

Price of fertilizers in the world are raising! Adding Jinkela in fertilizer, one bag can cover two bags!!

Although Jinkela has been sold for over 10 years, people from America, Africa, Japan are still lining up in a queue to buy it. Each person is given a unique id x. The country of each person can be identified by the remainder of his id divided by 3. If x mod 3 = 0, he is from America; if x mod 3 = 1, he is from Africa; if x mod 3=2, he is from Japan.

Lining up is tedious, everyone wants to cut in line! These American, African, and Japanese follow some rule when they cut in line:

When a person enters the queue,

1. If the queue is empty, he becomes the first person in the queue.
2. If there isn't anyone who comes from the same country in the queue, he becomes the last person in the queue.
3. Otherwise, of all people coming from the same country in the queue, he finds the last of them and lines up after him ( and possibly cuts in line ).

As old saying goes, "all humans are equal, but some humans are more equal than others." People with id of multiples of five are VIP. VIP enter another special queue instead of the normal one. All VIP are polite and highly educated, so they don't cut in the line.

Every time the supplier provides Jinkela with first person from both normal queue and VIP queue. After a person buys Jinkela, he leaves the queue immediately and will not enter the queue again.

You are curious about the order people get their Jinkela. Given the status of the queue. Whenever someone leaves the queue, output his id. If two people leave at once, output VIP id first and then the normal id.

Refer to the sample IO for example if you don't understand the rule.

---

For example, assume the queue is empty initially

• ENQUEUE 0: An American with id 0 enters the VIP queue.

queue:
VIP queue: 0

• ENQUEUE 1: An African with id 1 enters the queue. Since the queue is empty, he becomes the first person in the queue.

queue: 1
VIP queue: 0

• ENQUEUE 3: An American with id 3 enters the queue. Since there isn't any other American in the queue, he becomes the last person in the queue.

queue: 1 3
VIP queue: 0

• ENQUEUE 4: An African with id 4 enters the line. Since he finds an African (id=1) in the line, he lines up right after him.

queue: 1 4 3
VIP queue: 0

• ENQUEUE 7: An African with id 7 enters the line. He finds two African (id=1, id=4) in the line, where African with id 4 is the last one, he lines up after American with id 4.

queue: 1 4 7 3
VIP queue: 0

• ENQUEUE 10: An African with id 10 enters the VIP queue.

queue: 1 4 7 3
VIP queue: 0 10

• ENQUEUE 30: An American with id 30 enters the VIP queue. He says hi to American with id 0 but does not try to cut in line.

queue: 1 4 7 3
VIP queue: 0 10 30

• DEQUEUE: The first person of both queue leaves the line. Output VIP id(0) first and then normal id(1).

queue: 4 7 3
VIP queue: 10 30
output:“0 1”

• DEQUEUE: The first person of both queue leaves the line. Output VIP id(10) first and then normal id(4).

queue: 7 3
VIP queue: 30
output:“10 4”

• DEQUEUE: The first person of both queue leaves the line. Output VIP id(30) first and then normal id(7).

queue: 3
VIP queue:
output:“30 7”

• DEQUEUE: The first person of the normal queue leaves the line. Output normal id(3).

queue:
VIP queue:
output:“3”

---

Note

It is highly recommended to use IO optimization to avoid TLE in this problem.
Before submitting your answer to OJ, add these two lines of codes in the beginning of the main function.

We promise that if both queues are empty, no DEQUEUE will happen.

Input

Each line contains one instruction only.

• ENQUEUE x: person with id x enters the queue. x is an integer. 0<=x<=9*10^8
• DEQUEUE: the first person in both normal queue and VIP queue buy their Jinkela and leave the queue.

Please keep reading input until reach EOF.

For the first 3 testcases, the number of instructions ≤ 1000.

For the rest of the testcases, the number the number of instructions ≤ 1100000.

Output

For each DEQUEUE command, please output all ids who leave the queue.
Each output occupies a single line with a '\n' at the end of the line.
If two people are leaving at once, output the VIP id first and then the normal id, and seperate them with a single space.
Don’t output a space at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss