Пирамида Видений
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время расследования таинственных событий в Академии Невермор Уэнсдей находит древний дневник бывшей директрисы Лариссы Уимс. В нём содержится описание магического ритуала, в котором используется Пирамида Видений — древний артефакт, связанный с историей Проклятых и способный дать Уэнсдей подсказку в её расследовании.

Пирамида Видений представляет собой загадочный объект, состоящий из $$$n$$$ уровней. На $$$i$$$-м уровне находятся $$$i$$$ магических кристаллов, каждый кристалл содержит внутри себя запас тёмной энергии, выражаемый целым числом.

Ритуал призван разрушить данную пирамиду и происходит он по следующим правилам:

- Уровни разрушаются сверху вниз: сначала первый (верхний), затем второй и т. д., пока не будет разрушен предпоследний уровень. Нижний уровень (основание) не разрушается.
- Для разрушения уровня каждый кристалл на нём должен «передать» свою энергию сильнейшему из двух кристаллов под ним. Так как энергия тёмная, у кристалла, получающего энергию, она не увеличивается, а уменьшается на величину переданной ему энергии. Иначе говоря, пусть на некотором уровне стоит кристалл со значением $$$x$$$, а непосредственно под ним на следующем уровне находятся два кристалла со значениями $$$a$$$ (левый) и $$$b$$$ (правый), тогда:
  - если $$$a > b$$$, то энергия передаётся левому кристаллу, и его значение становится $$$a - x$$$;
  - если $$$a \leq b$$$, то энергия передаётся правому кристаллу, и его значение становится $$$b - x$$$;

После выполнения ритуала кристаллы основания Пирамиды Видений наполнятся необходимым количеством темной энергии и покажут пророчество о судьбе Академии и тайне, которую скрывала Ларисса Уимс.

Уэнсдей смогла выполнить ритуал — а сможете ли вы?

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

В первой строке задано целое число $$$n$$$ — количество уровней в Пирамиде Видений ($$$1 \le n \le 1000$$$).

Следующие $$$n$$$ строк описывают уровни пирамиды.

В $$$i$$$-й строке через пробел записаны $$$i$$$ целых чисел $$$a_{i, j}$$$, где $$$j$$$-е число описывает величину тёмной энергии, заключённой в $$$j$$$-м кристалле этой строки ($$$|a_{i, j}| \le 10^9$$$).

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

Выведите $$$n$$$ чисел — величины тёмной энергии кристаллов основания пирамиды после выполнения ритуала.

Примеры

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

    312 34 5 6

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

    4 3 4

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

    11000000000

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

    1000000000

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

    57-5 2-5 2 28 1 -4 88 -9 3 4 -2

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

    -5 -9 18 -2 -2