У Беси есть массив \(a_1, \ldots, a_N\), где \(1 \leq N \leq 300\) и
\(0 \leq a_i \leq 10^9\) для всех \(i\).
Она не хочет сообщать Вам сам массив \(a\), но может отвечать на ваши запросы
то есть для каждой пары индексов \(i \leq j\), Беси скажет Вам
\(r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]\).
По заданным значениям \(r\) сконструируйте массив, который мог бы быть
оригинальным массивом Беси. Значения в этом массиве должны быть в интервале
\([-10^9, 10^9]\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит число
\(N\).
Далее следуют \(N\) строк. \(i\)-ая из этих строк содержит число
\(r_{i, i}, r_{i, i + 1}, \ldots, r_{i, N}\).
Гарантируется, что существует некоторый массив с числами в интервале
\([0, 10^9]\) такой, что для всех \(i \leq j\),
\(r_{i, j} = \max a[i\ldots j] - \min a[i\ldots j]\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите одну строку, содержащую \(N\) целых чисел \(b_1, b_2, \ldots, b_N\)
в интервале \([-10^9, 10^9]\) представляющих Ваш массив. Они должны удовлетворять
\(r_{i, j} = \max b[i\ldots j] - \min b[i\ldots j]\) для всех \(i \leq j\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 2 2
0 1
0
|
1 3 2
|