Description
Price of fertilizers in the world are raising! Adding Jinkela in fertilizer, one bag can cover two bags!!
People from America, Africa, Japan are lining up in a queue to buy Jinkela. 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,
- If the queue is empty, he becomes the first person in the queue.
- If there isn't anyone who comes from the same country in the queue, he becomes the last person in the queue.
- 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 ).
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.
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 queue. Since the queue is empty, he becomes the first person in the queue
queue: 0
- ENQUEUE 1: An African with id 1 enters the queue. Since there isn't any other African in the queue, he becomes the last person in the queue.
queue: 0 1
- ENQUEUE 3: An American with id 3 enters the queue. Since he finds an American (id=0) in the line, he lines up right after him.
queue: 0 3 1
- ENQUEUE 6: An American with id 6 enters the line. He finds two American (id=0, id=3) in the line, where American with id 3 is the last one, he lines up after American with id 3.
queue: 0 3 6 1
- DEQUEUE: The first person leaves the line. Output his id(0).
queue: 3 6 1 output: 0
All of the above is the easy version problem discription.
Now, to avoid too many people cutting in line , there is a police officer around there. If the police is watching, no one can cut in line. They should become the last people in the line. However, the police may go have some donuts. If the police is not watching, the newer people who enter will follow the rules above.
In the beginning the police officer is having some donuts.
- POLICEWATCHING: The police is watching, no one can cut in line now!
POLICEWATCHING
- DONUTSTIME: The police is gone.
DONUTSTIME
Input
It is highly recommended to use IO optimization to avoid TLE in this problems.
ios_base::sync_with_stdio(false);
cin.tie(0);
The status of queue is represented as several commands.
Each line contains one of the following commands:
- ENQUEUE x: person with id x enters the queue. x is an integer, 0 ≦ x ≦ 3*10^8
- DEQUEUE: the first person in the queue buys his Jinkela and leaves the queue
- POLICEWATCHING: The police is watching, no one can cut in line now!
- DONUTSTIME: The police is gone.
Please keep reading input until reach EOF.
Output
For each DEQUEUE command, please output the id of person who leaves the queue.
Each output occupies a single line.
Tags