Problem Description

Bessie has an array \( a_1, \cdots, a_N \) where \( 1 \le N \le 300 \) and for all \( i \), \( 0 \le a_i \le 10^9 \). She won't tell you the array \( a \) itself, but she will tell you the range of each 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 values of \( r \), construct an array that could be Bessie's original array. The values in your array should be within the range \([-10^9, 10^9]\).

Input Format

The first line of input contains \( N \).

The next \( N \) lines, the \( i \)-th line contains integers \( r_{i,i}, r_{i,i+1}, \cdots, r_{i,N} \).

The input is guaranteed to exist such that there is an array \( a \) with values within the range \([0, 10^9]\) that satisfies 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 \) within the range \([-10^9, 10^9]\), representing your array. These numbers need to satisfy for all \( i \le j \) that \( r_{i,j} = \max a[i \cdots j] - \min a[i \cdots j] \).

Sample Input and Output

Sample Input #1

3
0 2 2
0 1
0

Sample Output #1

1 3 2

Sample Input #2

3
0 1 1
0 0
0

Sample Output #2

0 1 1

Sample Input #3

4
0 1 2 2
0 1 1
0 1
0

Sample Output #3

1 2 3 2

Sample Input #4

4
0 1 1 2
0 0 2
0 2
0

Sample Output #4

1 2 2 0

Notes

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.

Test Case Properties

• Test case 5 satisfies \( r_{1,N} \le 1 \).
• Test cases 6-8 satisfy \( r_{i,i+1} = 1 \) for all \( 1 \le i < N \).
• Test cases 9-14 have no additional constraints.

见题面 Input 部分

见题面 Output 部分