Загадан спрятанный массив \(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\) путем удаления нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца.
Выходные данные
Для каждого теста выведите одну строку, содержащую \(n\) положительных целых чисел \(a_1, a_2, \cdots a_n\) — любой допустимый массив \(a\). Обратите внимание, что \(a\) должен быть палиндромом.
Если существует несколько решений, выведите любое из них.
Примечание
Для первого примера, подмассивы массива \(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\) встречается только один раз во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|