题目描述

给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和的路径。例如：

最大和路径为： 13 8 26 15 24

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入格式

第 1 行一个数 n，范围 [1,100] ，给出三角形的行数；

第 2 到 n+1 行，第 i 行有 i-1 个整数，范围 [1,100]；

输出格式

n 个整数。数据保证最大和路径只有一条。

样例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

7 3 8 7 5