Knowledge Test about Match

题号：NC223599
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

It's classical to match two arrays to minimize the loss function, such as Network flow and Kuhn-Munkres algorithm. Here comes a small test.

You are given two sequences ${a,b}$ with length ${n}$ .

$a=\{0,1,2,\dots,n-2,n-1\},b=\{b_0,b_1,b_2,\dots,b_{n-2},b_{n-1}\}$ .

Now you are allowed to rearrage sequence $b$ arbitrarily. Formally, you can assign a permutation ${p}$ between ${0}$ to ${n-1}$ and do the following transformation: $b'_i=b_{p_i}$ .

Finally you should minimize the loss function $f(a,b)=\sum \limits_{i=0}^{n-1} \sqrt{|a_i-b_i|}$ .

Because the time limit is too strict to solve, you don't need to find the exact value of ${f(a,b)}$ . Denote the minimal value is $f_k^{\ast}$ and your result is $\hat f_k$ (where ${k}$ means the ${k}$ -th test case), you will be accepted if:

$\frac{1}{T}\sum \limits_{k=1}^T \frac{\hat {f_k} - f_k^{\ast}}{f_k^{\ast}} \le 4\%$

输入描述:

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first line contains an integer  indicating the length of sequences. The second line contains $n$ integers, describing the sequence $b$.

It's guaranteed that the sum of $n$ over all test cases does not exceed .

Notice: For each ,  is selected from  independently with equal probability. But the length of arrays in each test case can be assigned manually.

输出描述:

For each test case, output  integers in a line, indicating the sequence  after rearranging.

示例1

输入

复制

2
10
4 8 9 9 6 1 3 9 5 2
54
0 0 0 1 2 2 4 4 5 6 7 10 16 17 18 19 19 20 23 24 25 26 26 26 27 29 30 30 31 32
32 33 34 36 37 37 38 39 41 42 42 43 43 44 44 45 45 46 50 50 51 53 53 53

输出

复制

9 1 2 3 4 5 6 9 8 9
0 1 2 2 4 5 6 7 4 0 10 0 53 43 32 30 16 17 18 19 20 19 26 23 24 25 26 27 26 29
30 31 32 33 34 37 36 37 38 39 42 41 42 43 44 45 46 45 44 50 50 51 53 53

说明

The sample test doesn't obey  but the final tests obey.

For the first test case, the output reaches the optimal value. But for the second test case, the output is not optimal and the approximate ratio is .

So the average approximate ratio of the sample test is  without exceeding .