eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Города Нила

Города Нила

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Известно, что поселения на берегах Нила очень древние, и найдены ещё далеко не все. Один из археологов решил проанализировать обрывочные записи древних купцов и обнаружил, что они достаточно часто упоминают время, требуемое на доставку товара из одного поселения в другое. Зная скорость движения по реке в те далёкие времена, он легко перевёл время в расстояние между поселениями. Учёный знал, что на Ниле в изучаемое время было N поселений, одно из которых, в устье Нила, было известно. Он принял его положение за точку отсчёта. Из анализа записей о торговле он получил ровно N*(N-1)/2 расстояний между поселениями, т.е. расстояния между любыми двумя поселениями. Ему осталось только сопоставить расстояния парам поселений, и найти расположение поселений вдоль Нила. Потом, правда, он сообразил, что расположение поселений, найденное по указанной информации, может оказаться не единственным, и его энтузиазм несколько угас. Однако, информация лишней не бывает, и он решил всё же заказать программу, выдающую хотя бы одно расположение поселений.

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

В первой строке одно целое число N (число посёлков, 3N25).

Далее в N*(N-1)/2 строк все расстояния между посёлками, по одному целому положительному числу в строке, упорядоченные по возрастанию. Каждое расстояние не превышает 100 000.

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

Расстояния от устья Нила до каждого из N поселений, по одному в строке, упорядоченные по возрастанию. Расстояние до первого поселения всегда равно 0.

Пример

Входные данные #1
5
2
5
7
7
9
9
14
14
16
23
Выходные данные #1
0
9
14
16
23