Range Reconstruction

문제

Bessie has an array $a_1, \ldots, a_N$, where $1 \leq N \leq 300$ and $0 \leq a_i \leq 10^9$ for all $i$. She won't tell you $a$ itself, but she will tell you the range of each subarray of $a$. That is, for each pair of indices $i \leq j$, Bessie tells you $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$. Given these values of $r$, please construct an array that could have been Bessie's original array. The values in your array should be in the range $[-10^9, 10^9]$.

입력

The first line contains $N$.

Another $N$ lines follow. The $i$th of these lines contains the integers $r_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}$.

It is guaranteed that there is some array $a$ with values in the range $[0, 10^9]$ such that for all $i \leq j$, $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$.

출력

Output one line containing $N$ integers $b_1, b_2, \ldots, b_N$ in the range $[-10^9, 10^9]$ representing your array. They must satisfy $r_{i, j} = \max b[i\ldots j] - \min b[i\ldots j]$ for all $i \leq j$.

예제 입력 1

3
0 2 2
0 1
0

예제 출력 1

1 3 2

예제 입력 2

3
0 1 1
0 0
0

예제 출력 2

0 1 1

예제 입력 3

4
0 1 2 2
0 1 1
0 1
0

예제 출력 3

1 2 3 2

예제 입력 4

4
0 1 1 2
0 0 2
0 2
0

예제 출력 4

1 2 2 0

점수

Test 5 satisfies $r_{1,N} \leq 1$.Tests 6-8 satisfy $r_{i,i+1} = 1$ for all $1 \leq i < N$. Tests 9-14 satisfy no additional constraints.