10401040 SUSTech Online Judge
Problem 1040 --Magic Queue

## 1040: Magic Queue

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 544  Solved: 218
[Submit][Status][Web Board]

## Description

After last lecture, you must know a lot of queue. Queue is a FIFO list. But do you know magic queue? Magic queue is a queue which supports four operations:

Push_frist x: push an element x from the front of the queue.

Pop_first: pop an element x from the queue.

Push_last x: push an element x at the rear of the queue.

Pop_last:pop an element x at the rear of the queue.

(See more in the samples)

Now there is a magic queue and n operations. Please write a program which can display the element in the queue after n operations.

## Input

The first line will be an integer T, which is the number of test cases. (1 <= T <= 10)

For each test case, the first line will be an integer n (1 <= n <= 105)

Then there will be n lines, each line will be one of the following cases:

1 1 x: push_first x

1 2: pop_first

2 1 x: push_last x

2 2:pop_last

(0 <= x <= 103)

The input ensures that when you pop, there always are some elements in the queue.

## Output

For each test case, print the elements in the magic queue from the front to the rear. And each element should in a single line.

## Sample Input

1
8
1 1 1
1 1 2
1 1 3
2 1 1
2 1 2
2 1 3
1 2
2 2


## Sample Output

2
1
1
2


Median problem

[Submit][Status]