Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example.
In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.
Your task is to write a program that simulates such a team queue.
The input will contain one or more test cases. Each test case begins with the number of teams t (1<=t<=1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0 - 999999. A team may consist of up to 1000 elements. Finally, a list of commands follows. There are three different kinds of commands:
ENQUEUE x - enter element x into the team queue
DEQUEUE - process the first element and remove it from the queue
STOP - end of test case
The input will be terminated by a value of 0 for t.
Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the implementation of the team queue should be efficient: both enqueing and dequeuing of an element should only take constant time.
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 element which is dequeued on a single line. Print a blank line after each test case, even after the last one.
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001本题由oj和助教手动进行联合评测，未通过手动评测的将会由助教单独告知
在组队队列中，每个元素(element)属于一支队伍。如果一个元素将要进入组队队列时，它会先从头到尾检查它的队友(同属一支队伍)是否已经在队列里面了，如果找到了，它就会紧随其后进入队伍。如果没有找到，则它会从队列末尾入队，并成为自己队伍的第一个元素。出队操作则跟普通队列一样：元素在组队队列中按从头到尾的顺序出列。
就像你要排一支很长的队伍，但是不想从最后面排起，于是你从头到尾看看队伍里面有没有熟人在，如果有，你就插队到熟人后面，如果没有，就只能从队尾慢慢排了。。
具体实现：
题目的入队算法很简单：
搜索team queue里面是否存在同一个team的元素；
有的话，将该元素插入到team queue里面该队元素的最后一个之后；
没有的话，将该元素插入到队尾。
但是，team queue要用哪种数据结构实现呢？根据上面3点，这种数据结构必须是可以判断元素是否在队列内，以及从任意位置插入元素。
普通的队列无法实现在队列中间插入元素，也无法判断是否包含某一元素；
数组可以实现线性搜索，但是中间插入元素时开销巨大；
STL的vector容器可以判断是否包含，但是无法指定位置插入元素。
最后考虑到可以用优先队列实现。C++标准库中的priority_queue可以通过top()成员函数检索队列中的最大元素。因此排在组队队列前面的元素必须“大于”后面的元素，才可以通过优先队列的pop()操作首先出列。
那怎样判断元素的大小呢？
首先，首先进入queue的team，必须排在queue前面，即该team的元素相对比其他team大。可以设teamOrder来表示team进入queue的顺序；
其次，对于同一team的成员来说，越早进入queue的成员排名越前。可以设order表明所有元素入队顺序。