D. Отсутствующая сумма подмассива
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Загадан спрятанный массив $$$a$$$ из $$$n$$$ положительных целых чисел. Вы знаете, что $$$a$$$ является палиндромом, или, другими словами, для всех $$$1 \le i \le n$$$, $$$a_i = a_{n + 1 - i}$$$. Вам даны суммы всех, кроме одной, различных подмассивов этого массива, в произвольном порядке. Подмассив, сумма которого не дана, может быть любым из $$$\frac{n(n+1)}{2}$$$ различных подмассивов массива $$$a$$$.

Восстановите любой возможный палиндром $$$a$$$. Ввод выбран таким образом, что всегда существует по крайней мере один массив $$$a$$$, удовлетворяющий условиям.

Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца.

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

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 200$$$) — количество тестов. Затем следует описание тестов.

Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$3 \le n \le 1000$$$) — размер массива $$$a$$$.

Следующая строка каждого теста содержит $$$\frac{n(n+1)}{2} - 1$$$ целых чисел $$$s_i$$$ ($$$1\leq s_i \leq 10^9$$$) — все, кроме одной, суммы подмассивов массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$1000$$$.

Дополнительное ограничение на ввод: всегда существует по крайней мере одно допустимое решение.

Взломы в этой задаче отключены.

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

Для каждого теста выведите одну строку, содержащую $$$n$$$ положительных целых чисел $$$a_1, a_2, \cdots a_n$$$ — любой допустимый массив $$$a$$$. Обратите внимание, что $$$a$$$ должен быть палиндромом.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
7
3
1 2 3 4 1
4
18 2 11 9 7 11 7 2 9
4
5 10 5 16 3 3 13 8 8
4
8 10 4 6 4 20 14 14 6
5
1 2 3 4 5 4 3 2 1 1 2 3 2 1
5
1 1 2 2 2 3 3 3 3 4 5 5 6 8
3
500000000 1000000000 500000000 500000000 1000000000
Выходные данные
1 2 1 
7 2 2 7 
3 5 5 3 
6 4 4 6 
1 1 1 1 1 
2 1 2 1 2 
500000000 500000000 500000000
Примечание

Для первого примера, подмассивы массива $$$a = [1, 2, 1]$$$:

  • $$$[1]$$$ с суммой $$$1$$$,
  • $$$[2]$$$ с суммой $$$2$$$,
  • $$$[1]$$$ с суммой $$$1$$$,
  • $$$[1, 2]$$$ с суммой $$$3$$$,
  • $$$[2, 1]$$$ с суммой $$$3$$$,
  • $$$[1, 2, 1]$$$ с суммой $$$4$$$.
Таким образом, полный список сумм подмассивов: $$$1, 1, 2, 3, 3, 4$$$, и сумма, которая отсутствует во входном списке, равна $$$3$$$.

Для второго примера, отсутствующая сумма подмассива равна $$$4$$$ для подмассива $$$[2, 2]$$$.

Для третьего примера, отсутствующая сумма подмассива равна $$$13$$$, потому что существуют два подмассива с суммой $$$13$$$ ($$$[3, 5, 5]$$$ и $$$[5, 5, 3]$$$), но $$$13$$$ встречается только один раз во входных данных.