Города вдоль шоссе
На шоссе расположены несколько городов, и оно не имеет развилок. Зная расстояния между соседними городами, мы можем определить все расстояния от любого города до всех остальных. Например, если у нас есть пять городов (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'. Если ответа не существует, ничего не выводите. В конце вывода для каждого набора данных должна быть напечатана строка, содержащая пять минусов '—–' для удобства чтения. Лишние символы в выводе не допускаются, например, пробелы в конце строки.