Міста вздовж шосе
Є кілька міст, розташованих уздовж шосе, яке не має розгалужень. Знаючи відстані між сусідніми містами, ми можемо обчислити всі відстані від будь-якого міста до всіх інших. Наприклад, маючи п'ять міст (A, B, C, D і E) та відстані між сусідніми містами, як показано на Рисунку 1, ми можемо скласти матрицю відстаней у вигляді верхньої трикутної матриці, що містить відстані між усіма парами міст, як показано на Рисунку 2.
Рисунок 1: Приклад міст
Рисунок 2: Матриця відстаней для Рисунка 1
У цій задачі вам потрібно розв'язати обернену задачу. Ви знаєте лише відстані між усіма парами міст, тобто N(N −1)/2 чисел у наведеній вище матриці. Ваше завдання — відновити порядок міст і відстані від кожного міста до наступного.
Вхідні дані
Вхідні дані складаються з послідовності наборів даних. Кожен набір даних має такий формат:
N d_1 d_2 ... d_{N(N−1)/2}
Перша строка містить ціле число N (2 ≤ N ≤ 20), яке є кількістю міст на шосе. Наступні строки містять N(N−1)/2 цілих чисел, розділених пробілом або новим рядком, які є відстанями між усіма парами міст. Числа наведені в порядку спадання без будь-якої інформації про те, де вони з'являються в матриці. Ви можете припустити, що кожна відстань знаходиться в межах від 1 до 400, включно. Зверніть увагу, що найдовша відстань — це відстань від крайнього лівого міста до крайнього правого.
Кінець введення позначається рядком, що містить нуль.
Вихідні дані
Для кожного набору даних виведіть N−1 цілих чисел в одному рядку, кожне з яких є відстанню від одного міста до наступного в порядку міст. Числа в рядку повинні бути розділені одним пробілом. Якщо відповідь не є унікальною, виведіть кілька рядків, впорядкованих за лексикографічним порядком як послідовність цілих чисел, кожне з яких відповідає відповіді. Наприклад, '2 10' повинно передувати '10 2'. Якщо жодної відповіді не існує, нічого не виводьте. В кінці виводу для кожного набору даних повинен бути надрукований рядок, що містить п'ять мінусів '—–' для зручності читання. Жодних зайвих символів у виводі бути не повинно. Наприклад, зайві пробіли в кінці рядка не допускаються.