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]$$$。