Том вирішив підготувати хитру пастку для Джеррі. Він розклав шматочків сиру по колу. Кожен шматочок приносить Джеррі певне задоволення a_i — воно може бути навіть від’ємним, якщо Джеррі не любить цей вид сиру.
Том ще не визначив точні значення a_i, але він чудово знає поведінку Джеррі: якщо першим доступним шматочком буде -й, то Джеррі почне їсти за годинниковою стрілкою, з’ївши деякий (можливо, порожній) префікс цієї лінійної послідовності так, щоб максимізувати сумарне задоволення.
Нехай позначає максимальну суму елементів деякого (можливо, порожнього) префікса масиву .
Для кожного визначимо послідовність b_i як циклічний зсув масиву , що починається з його -го елемента:
тобто b_1 = a.
Відомо, що якщо першим доступним шматочком є -й, то сумарне задоволення Джеррі дорівнюватиме c_i = mx(b_i).
Єдине, що Том уже визначив, — це масив . Допоможіть йому знайти будь-який масив , для якого масив можна отримати відповідно до описаного вище правила.
У першому рядку задано ціле число — довжина масиву .
У другому рядку задано цілих чисел c_1, c_2, \dots, c_n — елементи масиву .
1 \le n \le 2 \cdot 10^5,
0 \le c_i \le 10^{12}.
Виведіть будь-який масив , для якого |a_i| \le 10^{18}, такий, що масив можна отримати з нього відповідно до умови.
Якщо існує декілька правильних відповідей, виведіть будь-яку з них.
Можна довести, що за наведених обмежень завжди існує принаймні один масив , який задовольняє умову.
Приклад
Приклад 1