Reconstruct the Array from Subarray Ranges

Bessie has an array \(a_1, \ldots, a_N\) where \(1 \le N \le 300\) and \(0 \le a_i \le 10^9\) for every \(i\). She will not reveal the array itself; instead, for every subarray you are given its range, that is, for every pair \(i \le j\) you are given

[ r_{i,j}=\max{a_i,\ldots,a_j}-\min{a_i,\ldots,a_j}. ]

Your task is to construct an array whose subarray ranges match the given values. Any valid array with each element in the range \([-10^9,10^9]\) will be accepted.

inputFormat

The input begins with a line containing a single integer \(N\) (the length of the array). The next \(N\) lines describe the values of \(r_{i,j}\): the \(i\)th line contains \(N-i+1\) space-separated integers representing \(r_{i,i}, r_{i,i+1}, \ldots, r_{i,N}\). Note that for every \(i\), \(r_{i,i}=0\).

outputFormat

Output a single line containing \(N\) space-separated integers, representing a valid array whose subarray ranges correspond to the given input.

sample

1
0

0