题目描述

$\red{namespace\_std }$在 $\red{E++ }$课上学会了快速排序。

这天的模拟赛上，第一题是一道排序的板子。他写了一个快速排序的代码，很快通过了样例并交了上 去。

然而，比赛结束前的两分钟，他意识到自己的快排忘记随机化了，并且他来不及修改了。

出成绩后，$\red{namespace\_std }$发现自己爆零了。

"按理说至少有暴力分啊，为什么会爆零啊……"

查看了一下测试数据，他发现数据损坏了，一些数字被替换为了 $\red{nan}$。

$\red{E++ }$定义，$\red{nan }$与 $\red{nan}$、$\red{nan }$与任何整数、任何整数与 $\red{nan }$比较的结果均为假！即：（以下为伪代码）

boolean operator < (Int x, Int y)
if isnan(x) or isnan(y)
then return false
else return x<y

$\red{namespace\_std }$的快排代码实现是： （以下为伪代码）

quicksort (Int[] A, int L, int R)
if L >= R
then return
Int Left <- A[L]
Int[] B
int Mid = L
int Bid = 0
for int i L+1 to R by 1 do
if A[i] < Left
then A[Mid] <- A[i]
Mid <- Mid + 1
else B[Bid] <- A[i]
Bid <- Bid + 1
end
for int i 0 to Bid - 1 by 1 do
A[Mid + i + 1] <- B[i]
A[Mid] <- Left
quicksort (A, L, Mid - 1)
quicksort (A, Mid + 1, R)

$\red{namespace\_std }$修好了数据，重测后得到了暴力分。但是他想知道自己的暴力在原来损坏的数据上的输 出。

输入格式

输入包含多组数据。第一行输入一个正整数$\red{T，}$表示数据组数。

之后对于每组数据，第一行是一个正整数$\red{n，}$代表要排序的数的个数；

接下来一行$\red{n}$个字符串，其要么是$\red{[1,le9]}$内的正整数，要么是字符串 $\red{nan}$。

其中$\red{1<=T<=10，}$$\red{1<=n<=5e5，}$$\red{n<=le6}$。

输出格式

对于每组数据，输出一行$\red{n}$个字符串，每个字符串是一个正整数或 $\red{nan，}$代表 $\red{namespace\_std }$的程序 排序后的结果。

样例

输入样例

3
4
2 4 1 3
7
nan 2 4 nan 1 nan 3
22
1 nan 1 nan 4 nan nan nan nan 5 nan nan nan nan nan 1 nan 4 nan nan nan nan

输出样例

1 2 3 4
nan 1 2 3 4 nan nan
1 nan 1 nan 1 4 nan nan nan nan 4 5 nan nan nan nan nan nan nan nan nan nan

提示

对于 $\red{12\% }$的数据，$\red{1<=n<=10 }$。

对于 $\red{24\% }$的数据，$\red{1<=n<=2000 }$。

另有 $\red{12\% }$的数据，输入中不包含 $\red{nan}$。

另有 $\red{24\% }$的数据，输入的每一个字符串有 $\red{50\% }$概率为 $\red{nan，}$有 $\red{50\% }$概率为一个$\red{[1,10^9]}$内均匀随机的 正整数。

另有 $\red{12\% }$的数据，每组数据中的字符串只包含至多一种正整数。

对于 $\red{100\% }$的数据，$\red{1<=T<=10，}$$\red{a<=n<=5\times 10^5，}$各组测试数据的$\red{n}$之和不超过$\red{10^6}$。