eolymp
bolt
Try our new interface for solving problems
Problems

Cities of the Nile

Cities of the Nile

Time limit 2 seconds
Memory limit 64 MiB

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

Input data

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

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

Output data

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

Examples

Input example #1
5
2
5
7
7
9
9
14
14
16
23
Output example #1
0
9
14
16
23