Range Reconstruction

문제

Bessie has an array $a_1,\dots ,a_{N}a\_1,\; \backslash ldots,\; a\_N$, where $1\le N\le 3001\; \backslash leq\; N\; \backslash leq\; 300$ and $0\le a_i\le {10}^{9}0\; \backslash leq\; a\_i\; \backslash leq\; 10^9$ for all $ii$. She won't tell you $aa$ itself, but she will tell you the range of each subarray of $aa$. That is, for each pair of indices $i\le ji\; \backslash leq\; j$, Bessie tells you $r_{i,j}=\max a[i\dots j]-\min a[i\dots j]r\_\{i,\; j\}\; =\; \backslash max\; a[i\backslash ldots\; j]\; -\; \backslash min\; a[i\backslash ldots\; j]$. Given these values of $rr$, 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][-10^9,\; 10^9]$.

입력

The first line contains $NN$.

Another $NN$ lines follow. The $ii$th of these lines contains the integers $r_{i,i},r_{i,i+1},\dots ,r_{i,N}r\_\{i,\; i\},\; r\_\{i,\; i\; +\; 1\},\; \backslash ldots,\; r\_\{i,\; N\}$.

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

출력

Output one line containing $NN$ integers $b_1,b_2,\dots ,b_{N}b\_1,\; b\_2,\; \backslash ldots,\; b\_N$ in the range $[-{10}^9,{10}^9][-10^9,\; 10^9]$ representing your array. They must satisfy $r_{i,j}=\max b[i\dots j]-\min b[i\dots j]r\_\{i,\; j\}\; =\; \backslash max\; b[i\backslash ldots\; j]\; -\; \backslash min\; b[i\backslash ldots\; j]$ for all $i\le ji\; \backslash leq\; j$.