Jumping the Queue

The beginning of a winter break near Spring Festival is always the beginning of a peak period of transportation. If you have ever tried to get a train ticket at that time, you must have witnessed the endless queues in front of every ticket box window. If a guy has seen his friend in a queue, then it is very much likely that this lucky guy might go straight to his friend and ask for a favor. This is called "jumping the queue". It is unfair to the rest of the people in the line, but, it is life. Your task is to write a program that simulates such a queue with people jumping in every now and then, assume that, if one in the queue has several friends asking for favors, he would arrange their requests in a queue of his own.

There will contain one or more test cases. Each test case begins with the number of groups n (1<= n <=1000). Then n group descriptions follow, each one consisting of the number of friends belonging to the group and those people's distinct names. A group is a friend group. People in one group are friend with each other. A name is a string of up to 4 characters chosen from {A, B, ..., Z, a, b, ..., z}. A group may consist of up to 1000 friends. You may assume that there is no one belong to two different groups.
Finally, a list of commands follows. There are three different kinds of commands:

● ENQUEUE X - Mr. or Ms. X goes into the queue
● DEQUEUE - the first person gets the ticket and leave the queue
● STOP - end of test case

The input will be terminated by a value of 0 for n.

For each test case, first print a line saying "Scenario #k", where k is the number of the test case. Then, for each DEQUEUE command, print the person who just gets a ticket on a single line. Print a blank line between two test cases, but no extra line at the end of output.

2
3 Ann Bob Joe
3 Zoe Jim Fat
ENQUEUE Ann
ENQUEUE Zoe
ENQUEUE Bob
ENQUEUE Jim
ENQUEUE Joe
ENQUEUE Fat
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 Anny Jack Jean Bill Jane
6 Eva Mike Ron Sony Geo Zoro
ENQUEUE Anny
ENQUEUE Eva
ENQUEUE Jack
ENQUEUE Jean
ENQUEUE Bill
ENQUEUE Jane
DEQUEUE
DEQUEUE
ENQUEUE Mike
ENQUEUE Ron
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP 
0

Scenario #1 
Ann
Bob
Joe
Zoe
Jim
Fat

Scenario #2 
Anny
Jack
Jean
Bill
Jane
Eva

You must maintain a hash table to store the names of the people, otherwise the efficiency of your program will not be acceptable since Judge's input file
is as large as about 12.5MB.

hjr

2008 HZNU Programming Contest