Description

Price of fertilizers in the world are raising! Adding Jinkela in fertilizer, one bag can cover two bags!!

People are lining up in a queue to buy Jinkela. Each person is given a unique id x. Lining up is tedious, so everyone wants to cut in line! These people 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 is a friend in line, he will queue after the last person among the friends;
• otherwise, he becomes the last person in the queue.

Some people may leave the queue without buying Jinkela, and these people may join the queue again.

You are curious about the order people get their Jinkela. Given the status of the queue, whenever someone gets his Jinkela, output his id.

Refer to the sample IO for example if you don't understand the rule.

Input

The first line contains two integers n m: the number of commands and the number of friend groups.

The following m lines are the friend groups, where, in each line, the first integer k is the number of the group members, and the next k integers are the id's of the group members. (Each person belongs to at most one group of friends.)

The following n lines are the commands, which can be:

• ENQUEUE x: the person with id x enters the queue;
• LEAVE x: the person with id x leaves the queue; 
• DEQUEUE: the first person in the queue buys his Jinkela and leaves the queue.

Testcases: 

• Cases 1~3: Without LEAVE commands; 1 <= n, x, k <= 1000, m = 3; everyone belongs to a group, and two persons are in the same group if the remainders are the same when their id's are divided by m. 
• Cases 4~6: Without LEAVE commands; 1 <= n, x, m <= 100000, 1 <= k <= 100.
• Cases 7~9: Without LEAVE commands; 1 <= n, m <= 100000, 1 <= x <= 2147483647, 1 <= k <= 100.
• Cases 10~12: With LEAVE commands; 1 <= n, m, k <= 1000, 1 <= x <= 100000; having LEAVEed the queue, a person will not enter the queue again.
• Case 13: With LEAVE commands; 1 <= n, x, m <= 100000, 1 <= k <= 100; having LEAVEed the queue, a person will not enter the queue again. 
• Case 14: With LEAVE commands; 1 <= n, m <= 100000, 1 <= x <= 2147483647, 1 <= k <= 100.

In addition, for each "LEAVE x" command, it is guaranteed that the person with id x must be in the queue.

Hint:

The 13rd & 14th testcases are more challenging. For the LEAVE commands, find some way to avoid "leaving the queue immediately".

Output

For each DEQUEUE command, please output the id of the person who buys his Jinkela and leaves the queue. If the queue is empty, output "The queue is empty".

Each output occupies a single line. Remember to add a '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss