题目描述

定义一个双端队列，进队操作与普通队列一样，从队尾进入。出队操作既可以从队头，也可以从队尾。编程实现这个数据结构。

输入格式

第一行输入一个整数 $t$，代表测试数据的组数。

每组数据的第一行输入一个整数 $n$，表示操作的次数。

接着输入 $n$ 行，每行对应一个操作，首先输入一个整数 $type$：

• 当 $type=1$ 时，为进队操作，接着输入一个整数 $x$，表示进入队列的元素；
• 当 $type=2$ 时，为出队操作，接着输入一个整数 $c$，$c=0$ 代表从队头出队，$c=1$ 代表从队尾出队。

输出格式

对于每组测试数据，输出执行完所有操作后队列中剩余的元素，元素之间用空格隔开，按队头到队尾的顺序输出，占一行。如果队列中已经没有任何元素，输出 NULL。

样例

2
5
1 2
1 3
1 4
2 0
2 1
6
1 1
1 2
1 3
2 0
2 1
2 0

3
NULL

数据范围

• $1 \le n \le 1000$
• $t$ 为较小的正整数，保证所有操作合法（出队时队列非空）。