零点的钟声敲响，猴年终于到来啦~

在这新年的第一天，猴族首领猴腮雷自然是要接受来自世界各地的朝贡的。在种类繁多的礼品中，魔仙堡女王送来的栈引起了他的注意——他发现这个栈的大小正好适合来装他的腮雷。

但是遗憾的是，因为种种原因，这个栈的底部破了，所以猴族首领猴腮雷让手下的工匠在这个栈的底部装了一个阀门，于是猴族首领猴腮雷不仅可以从这个栈的顶端取出它的腮雷，还能打开栈底的阀门，从最下面取出腮雷！

猴族首领猴腮雷有 $n$ 个腮雷，编号为 $i$ 的腮雷的威力是 $A_i$，而且任意两颗腮雷的威力都是不同的。现在他想用这个栈来整理这些腮雷，每时每刻他可以进行下面三种操作中的一种：

1. 入栈：如果当前还有腮雷没有被放入过栈中，那么就把剩下的腮雷中编号最小的放到栈中（作为新的栈顶）。
2. 出栈：如果当前栈中有腮雷，那么就把栈顶（即栈中最后被放入的）的腮雷取出来。
3. 打开阀门：如果当前栈中有腮雷，那么就把栈底（即栈中最先被放入的）的腮雷取出来。

在所有腮雷都从栈中取出后，猴腮雷按照腮雷出栈的时间顺序排成一排，再把这些腮雷的威力记录下来，这样就得到了一个数列 $B$。现在猴腮雷想让这个数列的字典序尽可能的小，但是因为他日理万机，没有时间来想这种简单的小问题，于是他就让你来帮他求出字典序最小的数列 $B$。

对于两个长度为 $n$ 的数列 $a$ 和 $b$，$a$ 的字典序小于 $b$ 当且仅当存在一个整数 $k\in [1,n]$ 满足 $a_i=b_i(1\le i<k)$ 且 $a_k<b_k$。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行包含一个正整数 $n$。

接下来一行 $n$ 个正整数 $A_1,\dots ,A_n$。

输出格式

对于每组数据，输出一行 $n$ 个正整数，表示字典序最小的数列 $B$ 。

样例一

input

2
3
1 2 3
4
1 3 4 2

output

1 2 3
1 2 3 4

explanation

对于第一组数据，重复入栈、出栈这两个操作三次，即可得到最优解。

对于第二组数据，最优的操作序列如下：入栈，出栈，入栈，入栈，入栈，出栈，打开阀门，出栈。

样例二

见样例数据下载。

限制与约定

对于所有数据，保证 $1\le T\le 5$，$1\le A_i\le {10}^9$ 。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载