← 返回题目列表

Codeforces · 1857/C

C. 通过最低限度组装

中文机器翻译题面 查看原题

Sasha 有一个包含 $$$n$$$ 整数的数组 $$$a$$$。他感到无聊,对于所有 $$$i$$$、$$$j$$$ ($$$i < j$$$),他写下了 $$$a_i$$$ 和 $$$a_j$$$ 的最小值。他获得了一个新数组$$$b$$$,大小为$$$\frac{n\cdot (n-1)}{2}$$$。

例如,如果 $$$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\le t\le 200$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^3$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$\frac{n\cdot (n-1)}{2}$$$ 整数 $$$b_1,b_2,\dots,b_{\frac{n\cdot (n-1)}{2}}$$$ ($$$−10^9\le b_i\le 10^9$$$) — 数组的元素$$$b$$$。

保证所有测试的$$$n$$$总和不超过$$$10^3$$$,并且对于测试中的每个数组$$$b$$$,都存在一个原始数组。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的任何可能的数组 $$$a$$$。

示例

输入 #1

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

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

注意

在第一个示例中,Sasha 选择了数组 $$$[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]$$$。