Range Reconstruction

Bessie has an array $a_{1}, \dots, a_{N}$ , where $1 \leq N \leq 300$ and $0 \leq a_{i} \leq 1 0^{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 \dots j] - min a [i \dots 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 $[- 1 0^{9}, 1 0^{9}]$ .

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

This example satisfies the constraints for subtask 1.

This example satisfies the constraints for subtask 2.

SCORING:

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.

Problem credits: Danny Mittal

Source: USA Computing Olympiad.

Input Format

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}, \dots, r_{i, N}$ .

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

Output Format

Output one line containing $N$ integers $b_{1}, b_{2}, \dots, b_{N}$ in the range $[- 1 0^{9}, 1 0^{9}]$ representing your array. They must satisfy $r_{i, j} = max b [i \dots j] - min b [i \dots j]$ for all $i \leq j$ .

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

Submit

Language