310596: CF1857C. Assembly via Minimums

C. Assembly via Minimumstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Sasha has an array $a$ of $n$ integers. He got bored and for all $i$, $j$ ($i < j$), he wrote down the minimum value of $a_i$ and $a_j$. He obtained a new array $b$ of size $\frac{n\cdot (n-1)}{2}$.

For example, if $a=$ [$2,3,5,1$], he would write [$\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)$] $=$ [$2, 2, 1, 3, 1, 1$].

Then, he randomly shuffled all the elements of the array $b$.

Unfortunately, he forgot the array $a$, and your task is to restore any possible array $a$ from which the array $b$ could have been obtained.

The elements of array $a$ should be in the range $[-10^9,10^9]$.

Input

The first line contains a single integer $t$ ($1\le t\le 200$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\le n\le 10^3$) — the length of array $a$.

The second line of each test case contains $\frac{n\cdot (n-1)}{2}$ integers $b_1,b_2,\dots,b_{\frac{n\cdot (n-1)}{2}}$ ($−10^9\le b_i\le 10^9$) — the elements of array $b$.

It is guaranteed that the sum of $n$ over all tests does not exceed $10^3$ and for each array $b$ in the test, there exists an original array.

Output

For each test case, output any possible array $a$ of length $n$.

ExampleInput

5
3
1 3 1
2
10
4
7 5 3 5 3 3
5
2 2 2 2 2 2 2 2 2 2
5
3 0 0 -2 0 -2 0 0 -2 -2

Output

1 3 3
10 10
7 5 3 12
2 2 2 2 2
0 -2 0 3 5

Note

In the first sample, Sasha chose the array $[1,3,3]$, then the array $b$ will look like $[\min(a_1,a_2)=1, \min(a_1,a_3)=1, \min(a_2,a_3)=3]$, after shuffling its elements, the array can look like $[1,3,1]$.

In the second sample, there is only one pair, so the array $[10,10]$ is suitable. Another suitable array could be $[15,10]$.

题目大意：
萨沙有一个由n个整数组成的数组a。他无聊的时候，对于所有的i, j (i < j)，他记录下了a_i和a_j的最小值。他得到了一个大小为n*(n-1)/2的新数组b。

例如，如果a=[2,3,5,1]，他会写下[min(2, 3), min(2, 5), min(2, 1), min(3, 5), min(3, 1), min(5, 1)] = [2, 2, 1, 3, 1, 1]。

然后，他随机打乱数组b的所有元素。

不幸的是，他忘记了数组a，你的任务是恢复任何可能的数组a，从数组b中可以获得。

数组a的元素应该在范围[-10^9,10^9]内。

输入数据格式：
第一行包含一个整数t (1≤ t≤ 200) —— 测试用例的数量。
每个测试用例的第一行包含一个整数n (2≤ n≤ 10^3) —— 数组a的长度。
每个测试用例的第二行包含n*(n-1)/2个整数b_1,b_2,…,b_(n*(n-1)/2) (-10^9≤ b_i≤ 10^9) —— 数组b的元素。
保证所有测试中n的总和不超过10^3，并且对于测试中的每个数组b，都存在一个原始数组。

输出数据格式：
对于每个测试用例，输出长度为n的任意可能的数组a。

示例：
输入：
5
3
1 3 1
2
10
4
7 5 3 5 3 3
5
2 2 2 2 2 2 2 2 2 2
5
3 0 0 -2 0 -2 0 0 -2 -2

输出：
1 3 3
10 10
7 5 3 12
2 2 2 2 2
0 -2 0 3 5

说明：
在第一个示例中，萨沙选择了数组[1,3,3]，然后数组b将看起来像[min(a_1,a_2)=1, min(a_1,a_3)=1, min(a_2,a_3)=3]，在打乱其元素后，数组可以看起来像[1,3,1]。
在第二个示例中，只有一个对，所以数组[10,10]是合适的。另一个合适的数组可能是[15,10]。题目大意： 萨沙有一个由n个整数组成的数组a。他无聊的时候，对于所有的i, j (i < j)，他记录下了a_i和a_j的最小值。他得到了一个大小为n*(n-1)/2的新数组b。 例如，如果a=[2,3,5,1]，他会写下[min(2, 3), min(2, 5), min(2, 1), min(3, 5), min(3, 1), min(5, 1)] = [2, 2, 1, 3, 1, 1]。 然后，他随机打乱数组b的所有元素。 不幸的是，他忘记了数组a，你的任务是恢复任何可能的数组a，从数组b中可以获得。 数组a的元素应该在范围[-10^9,10^9]内。 输入数据格式： 第一行包含一个整数t (1≤ t≤ 200) —— 测试用例的数量。 每个测试用例的第一行包含一个整数n (2≤ n≤ 10^3) —— 数组a的长度。 每个测试用例的第二行包含n*(n-1)/2个整数b_1,b_2,…,b_(n*(n-1)/2) (-10^9≤ b_i≤ 10^9) —— 数组b的元素。 保证所有测试中n的总和不超过10^3，并且对于测试中的每个数组b，都存在一个原始数组。 输出数据格式： 对于每个测试用例，输出长度为n的任意可能的数组a。 示例： 输入： 5 3 1 3 1 2 10 4 7 5 3 5 3 3 5 2 2 2 2 2 2 2 2 2 2 5 3 0 0 -2 0 -2 0 0 -2 -2 输出： 1 3 3 10 10 7 5 3 12 2 2 2 2 2 0 -2 0 3 5 说明： 在第一个示例中，萨沙选择了数组[1,3,3]，然后数组b将看起来像[min(a_1,a_2)=1, min(a_1,a_3)=1, min(a_2,a_3)=3]，在打乱其元素后，数组可以看起来像[1,3,1]。 在第二个示例中，只有一个对，所以数组[10,10]是合适的。另一个合适的数组可能是[15,10]。