C. Построение по минимумам
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У мальчика Саши есть массив $$$a$$$ из $$$n$$$ целых чисел. Ему стало скучно, и для всех $$$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$$$ существует исходный массив.

Выходные данные

Для каждого теста выведите любой возможный массив $$$a$$$ длиной $$$n$$$.

Пример
Входные данные
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]$$$.