【题目描述】

Bessie 有一个数组 a1,…,aN，其中 1≤N≤300 并对于所有 i 有 0≤ai≤10^9。她不会告诉你数组 a 本身，但她会告诉你 a 的每个子数组的全距。也就是说，对于每对索引 i≤j，Bessie 告诉你 ri,j=max a[i…j]−min a[i…j]。给定这些 r 的值，构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在[−10^9,10^9] 范围内。

【输入格式】（从终端 / 标准输入读入）：

输入的第一行包含 N。

以下 N 行，第 i 行包含整数 ri,i,ri,i+1,…,ri,N。

输入保证存在某个数组 a，其中的数值在 [0,10^9] 范围内，满足对于所有的 i≤j，有 ri,j=max a[i…j]−min a[i…j]。

【输出格式】（输出至终端 / 标准输出）：

输出一行，包含 N 个整数 b1,b2,…,bN，在[−10^9,10^9] 范围内，表示你的数组。这些数需要满足对于所有的 i≤j 有 ri,j=max a[i…j]−min a[i…j]。

【输入样例】：

3

0 2 2

0 1

0

【输出样例】：

1 3 2

【样例说明】

例如，r1,3=max a[1…3]−min a[1…3]=3−1=2。

【输入样例】：

3

0 1 1

0 0

0

【输出样例】：

0 1 1

【样例说明】

这个样例满足子任务 1 的限制。

【输入样例】：

4

0 1 2 2

0 1 1

0 1

0

【输出样例】：

1 2 3 2

【样例说明】

这个样例满足子任务 2 的限制。

【输入样例】：

4

0 1 1 2

0 0 2

0 2

0

【输出样例】：

1 2 2 0

【测试点性质】：

测试点 5 满足 r1,N≤1。

测试点 6-8 满足对于所有1≤i<N 均有 ri,i+1=1。

测试点 9-14 没有额外限制。