You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

namespace_std 在 E++ 课上学会了快速排序。

这天的模拟赛上，第一题是一道排序的板子。他写了一个快速排序的代码，很快通过了样例并交了上去。 然而，比赛结束前的两分钟，他意识到自己的快排忘记随机化了，并且他来不及修改了。 出成绩后，namespace_std 发现自己爆零了。

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

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

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

namespace_std 的快排代码如下所示。以下为伪代码，选手目录下的 qsort/qsort_example.cpp 中有此伪代码的 C++ 实现，供选手参考使用。

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

【输入数据】

从文件 ***qsort.in*** 中读入数据。

输入包含多组数据。

输入的第一行是一个正整数 ​T​，表示数据组数。

接下来是 T 组数据的描述。

对于每组数据的描述，第一行是一个正整数 ​n​，代表要排序的数的个数，接下来一行是 n 个字符串，其要么是 [1*,* 10^9^​^ ^​] 内的正整数，要么是字符串 nan。

【输出数据】

输出到 ***qsort.out*** 中。

对于每组数据，输出一行，包含 n 个字符串，每个字符串是一个正整数或 nan，代表

namespace_std 的程序排序后的结果。

【样例输入1】

见选手目录下的 ​qsort/qsort1.in​。

由于此测试点中第三组数据过长，此处略去。

2

4

2 4 1 3

7

nan 2 4 nan 1 nan 3

【样例输出1】

见选手目录下的 ​qsort/qsort1.ans​。

由于此测试点中第三组数据过长，此处略去。

1 2 3 4
nan 1 2 3 4 nan nan

【样例输入2/3】

见选手目录下的 qsort/qsort​​2​***.in*** 和 qsort/qsort​​2​***.ans***

见选手目录下的 qsort/qsort3.in 和 qsort/qsort3.ans

【数据范围】

对于 12% 的数据，1 ≤ n ≤ 10。

对于 24% 的数据，1 ≤ n ≤ 2000。

对于另外 12% 的数据，输入中不包含 nan。

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

对于另外 12% 的数据，每组数据中的字符串只包含至多一种正整数。

对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ n ≤ 5 × 10​^5^​，各组测试数据的 n 之和不超过 10​^6^​。