Data structures contest - high level
Student's queue in a canteen
In ADA University students like Programming competitions very much, so each student belongs to one (and only one) team. But the rules of different competitions are different, and not usually one team consists of 3 members like according to ACM rules. Any team can contain any number of students (but of course more than 0).
Students like to come to their canteen which is a building C and spent their free time with a cup of coffee. Students in ADA are very smart, they do not want to stand in standard queue for delicious coffee. They decided to establish some rules that only they would follow.
If a student enters the queue, he first searches the queue from head to tail to check if some of his teammates (student of the same team) are already in the queue. If yes, he enters the queue right behind them (behind all his teammates). If not, he enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: students are processed from head to tail in the order they appear in the queue.
Your task is to write a program that simulates such a queue.
First line contains number of teams t (1 ≤ t ≤ 1000). Each of the next t lines describes one team. First element in the line is the number n (1 ≤ n ≤ 1000) of students in a team. Next n integers in a line give the ID's (0 ≤ ID ≤
106) of students in a team.
Finally, a list of commands follows. There are two different kinds of commands:
- ENQUEUE x — student x enters into the queue
- DEQUEUE — process the first student and remove him from the queue
For each DEQUEUE command print the element which is dequeued on a single line.
2 3 1 2 3 3 4 5 6 ENQUEUE 1 ENQUEUE 4 ENQUEUE 2 ENQUEUE 5 ENQUEUE 6 ENQUEUE 3 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE
1 2 3 4 5 6
2 3 1 2 3 3 4 5 6 ENQUEUE 1 ENQUEUE 4 ENQUEUE 2 DEQUEUE DEQUEUE ENQUEUE 5 ENQUEUE 3 ENQUEUE 6 DEQUEUE DEQUEUE DEQUEUE DEQUEUE
1 2 4 5 6 3
3 3 11 12 13 3 24 25 26 3 47 48 49 ENQUEUE 11 ENQUEUE 47 ENQUEUE 48 ENQUEUE 12 ENQUEUE 24 ENQUEUE 49 DEQUEUE DEQUEUE DEQUEUE ENQUEUE 13 DEQUEUE DEQUEUE DEQUEUE
11 12 47 48 49 24