IITKESO207PA1Q2 - Queues

In this problem, you have to implement queues in C/C++. There are  operations that you must implement.

1) Enqueue : Takes an element and adds it to the back of the queue.

2) Dequeue: Removes the first element in the queue.

3) Is_Empty : Returns true if the queue is empty, false otherwise.

Note: Using standard library implementation is NOT allowed and will be considered cheating. The penalty shall be applied as it given in the handout is for cheating cases.

Input

First line contains t: the number of test cases. Each test case has lines.

The first line contains q, the number of queries. q lines follow.

Each query is has one or two space separated integers. The first is the opcode. 1 for Enqueue, 2 for Dequeue and 3 for Is_Empty.

If the opcode is 1, then there is another argument x that denotes the element to be enqueued. The opcodes 2 and 3 are not followed by any number.

Output

The output is as follows:

For the Dequeue operation output the element that has been dequeued. If the queue is empty and a dequeue operation is asked, print "Empty" (without quotes).

For the Is_Empty operation output True/False.

For the Enqueue opearation, print the element enqueued.

Constraints

1 <= t <= 10
1 <= q <= 1000000
1 <= x <= 10^9

Example

Input:
1
7
1 3
1 4
2
3
2
2
3
Output:
3
4
3
False
4
Empty
True

Explanation

The first line of the input says that there is only 1 test case.

The second line says there will be 7 queries.

The third line is 1 3 which means that we must enqueue 3 to the queue; the output is 3. Fourth line says that we enqueue 4 to the queue; the output is 4.

The fifth line asks for a dequeue operation and the output should be 3. The sixth line asks whether the queue is empty or not and the answer is False.


Added by:Programming Club, IITK
Date:2018-01-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C NCSHARP C++ 4.3.2 CPP CPP14 C99 JULIA PYPY3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.