qym 的快速排序

题目描述

qym 最近学习了快速排序

他学习的快速排序的写法是这样的：

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)

但是他怎么测试都发现代码运行错误，检查数据以后发现，原来是数据发生了错误，读取就报错了

数据中存在一些数字变成了乱码，这里我们统一用 nan 来表示错误数据

现在 qym 想修复一下自己的程序，让程序能够正确读取 nan 这个数据，并且进行排序

为了方便理解，qym 认为 nan 和 nan 以及任何数字进行任何比较的结果均为 false

以在排序中常用的 < 比较举例

nan < 3 的结果为 false nan < nan 的结果为 false 3 < nan 的结果为 false

qym 想知道，修复完以后，对于一份给定的输入数据，这份代码的输出会是什么？

输入格式

输入包含多组数据。第一行输入一个正整数 $T$，表示数据组数。 之后对于每组数据，第一行是一个正整数 $n$，代表要排序的数的个数； 接下来一行 $n$ 个字符串，其要么是 $[1, 1e9]$ 内的正整数，要么是字符串 nan

输出格式

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

数据范围

对于 $12\%$ 的数据，满足 $1 \leq n \leq 10$ 对于 $24\%$ 的数据，满足 $1 \leq n \leq 2000$ 对于 $100\%$ 的数据，满足 $1 \leq T \leq 10, 1 \leq n \leq 5 * 10^5, \sum{n} \leq 10^6$ 。 特别的满足 $12\%$ 的数据，输入不包含 nan

样例输入

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