У Бесі є масив \(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] \).

Формат вхідних даних

Перший рядок містить число \(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]\).

Формат вихідних даних

Виведіть один рядок, що містить \(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\).

Приклад вхідних даних

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 \(r_{i,i+1} = 1\) для всіх \(1 \leq i < N\).
• У тестах 9-14 немає додаткових обмежень.