Вчора в Ірини був день народження і їй подарували два масиви, один містить числа до ~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