题目描述

调查永不复学院发生的神秘事件时，星期三发现了前任校长拉丽莎·威姆斯的一本古老日记。其中记载了一项使用幻象金字塔的魔法仪式。幻象金字塔是一件与被诅咒者的历史有关的古代神器，能够为星期三的调查提供线索。

幻象金字塔是一个由 $n$ 层组成的神秘物体。第 $i$ 层有 $i$ 颗魔法水晶，每颗水晶内部储存的黑暗能量用一个整数表示。

仪式将按照以下规则摧毁金字塔：

• 各层从上到下依次被摧毁：先摧毁第一层，也就是最顶层，然后摧毁第二层，依此类推，直到倒数第二层被摧毁。最底层，也就是底座，不会被摧毁。
• 同一层内的水晶从左到右依次传递能量。每次传递后立即更新下一层对应水晶的数值，后续传递使用更新后的数值。
• 要摧毁某一层，该层的每颗水晶都必须将自己的能量“传递”给正下方两颗水晶中较强的那颗。由于这是黑暗能量，接收能量的水晶的能量不会增加，而会减去传入的能量。换言之，设某颗水晶的数值为 $x$，下一层正下方的两颗水晶的数值分别为 $a$（左侧）和 $b$（右侧），则：若 $a>b$，将能量传给左侧水晶，其数值变为 $a-x$；若 $a\le b$，将能量传给右侧水晶，其数值变为 $b-x$。

仪式完成后，幻象金字塔底座的水晶将充满所需的黑暗能量，显现出有关学院命运以及拉丽莎·威姆斯所隐瞒秘密的预言。

星期三成功完成了仪式，你也能做到吗？

输入格式

第一行包含一个整数 $n$，表示幻象金字塔的层数，$1\le n\le 1000$。

接下来 $n$ 行描述金字塔的各层。第 $i$ 行包含 $i$ 个用空格分隔的整数 $a_{i,j}$，其中第 $j$ 个整数表示这一层第 $j$ 颗水晶储存的黑暗能量，$|a_{i,j}|\le 10^9$。

输出格式

输出 $n$ 个整数，表示仪式完成后金字塔底座各颗水晶的黑暗能量。

3
1
2 3
4 5 6

4 3 4

1
1000000000

1000000000

5
7
-5 2
-5 2 2
8 1 -4 8
8 -9 3 4 -2

-5 -9 18 -2 -2