Description

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

Input Format

The first line contains $N$.

The next $N$ lines: line $i$ contains the integers $r_{i,i},r_{i,i+1}, \cdots ,r_{i,N}$.

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

Output Format

Output one line containing $N$ integers $b_1,b_2, \cdots ,b_N$ in the range $[−10^9,10^9]$, representing your array. These numbers must satisfy that for all $i \le j$, $r_{i,j}= \max a[i \cdots j]−\min a[i\cdots j]$.

3
0 2 2
0 1
0

1 3 2

3
0 1 1
0 0
0

0 1 1

4
0 1 2 2
0 1 1
0 1
0

1 2 3 2

4
0 1 1 2
0 0 2
0 2
0

1 2 2 0

Hint

Sample 1 Explanation

For example, $r_{1,3}=\max a[1 \cdots 3]−\min a[1\cdots 3]=3−1=2$.

Sample 2 Explanation

This sample satisfies the constraints of subtask 1.

Sample 3 Explanation

This sample satisfies the constraints of subtask 2.

Properties of test points

• Test point $5$ satisfies $r_{1,N} \le 1$.
• Test points $6-8$ satisfy that for all $1 \le i<N$ we have $r_{i,i+1}=1$.
• Test points $9-14$ have no additional constraints.

Translated by ChatGPT 5