Problem 3. Range Reconstruction

USACO 2022 December Contest, Silver

Bessie 有一个数组 $a_1, \ldots, a_N$，其中 $1 \leq N \leq 300$ 并对于所有 $i$ 有 $0 \leq a_i \leq 10^9$。她不会告诉你数组 $a$ 本身，但她会告诉你 $a$ 的每个子数组的全距。也就是说，对于每对索引 $i \leq j$，Bessie 告诉你 $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$。给定这些 $r$ 的值，构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在 $[-10^9, 10^9]$ 范围内。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

以下 $N$ 行，第 $i$ 行包含整数 $r_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}$。

输入保证存在某个数组 $a$，其中的数值在 $[0, 10^9]$ 范围内，满足对于所有的 $i \leq j$，有 $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$。

输出格式（输出至终端 / 标准输出）：

输出一行，包含 $N$ 个整数 $b_1, b_2, \ldots, b_N$，在 $[-10^9, 10^9]$ 范围内，表示你的数组。这些数需要满足对于所有的 $i \leq j$ 有 $r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]$。

输入样例：

3
0 2 2
0 1
0

输出样例：

1 3 2

例如，$r_{1, 3} = \max a[1\ldots 3] - \min a[1\ldots 3] = 3 - 1 = 2$。

输入样例：

3
0 1 1
0 0
0

输出样例：

0 1 1

这个样例满足子任务 1 的限制。

输入样例：

4
0 1 2 2
0 1 1
0 1
0

输出样例：

1 2 3 2

这个样例满足子任务 2 的限制。

输入样例：

4
0 1 1 2
0 0 2
0 2
0

输出样例：

1 2 2 0

测试点性质： 测试点 5 满足 $r_{1,N} \leq 1$。测试点 6-8 满足对于所有 $1 \leq i < N$ 均有 $r_{i,i+1} = 1$。测试点 9-14 没有额外限制。

供题：Danny Mittal