Вчора в Ірини був день народження і їй подарували два масиви, один містить числа до \(10^9\), а другий – суми двох сусідніх елементів попереднього масиву. Іринка довго ним гралась, і втомлена пішла спати, а коли вона прокинулася, то побачила, що в першому масиві замість деяких чисел хтось залишив -1. А ось другий масив ніхто не чіпав.

Іринка знає, що за цими даними, можна відновити початковий масив, але вона не в силах зараз думати. Допоможіть їй, знайдіть початковий масив. Гарантується, що в початковому масиві залишилось як мінімум одне число.

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

Перший рядок містить ціле число \(n\) \((2 \le n \le 10^5)\) – розмір першого масиву.

В наступному рядку йде \(n\) натуральних чисел першого масиву.

В третьому рядку \(n-1\) натуральне число - суми двох сусідніх чисел першого масиву.

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

Виведіть один рядок з \(n\) натуральних чисел – числа початкового масиву.

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

5
-1 -1 -1 -1 5
3 5 7 9

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

1 2 3 4 5