e-olymp
Competitions

Implementation: Data Structures

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.

Input

First line contains number of teams t (1t1000). Each of the next t lines describes one team. First element in the line is the number n (1n1000) of students in a team. Next n integers in a line give the ID's (0ID106) 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

Output

For each DEQUEUE command print the element which is dequeued on a single line.

Time limit 1 second
Memory limit 128 MiB
Input example #1
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
Output example #1
1
2
3
4
5
6
Input example #2
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
Output example #2
1
2
4
5
6
3
Input example #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
Output example #3
11
12
47
48
49
24 
Author Mykhailo Medvediev