Dany jest ciąg $a_1, a_2, \dots, a_n$. Możesz wykonać dowolną liczbę razy następującą operację:

• Wybierz $i$ i zastąp $a_i$ wartością $-(a_1+a_2+\cdots+a_n)$.

Znajdź leksykograficznie najmniejszy ciąg $a$, jaki można uzyskać.

Wejście

W pierwszej linii znajduje się liczba całkowita dodatnia $n$.

W drugiej linii znajduje się $n$ liczb całkowitych, podanych w kolejności niemalejącej, reprezentujących $a_i$.

Wyjście

Wypisz w jednej linii $n$ liczb całkowitych, reprezentujących leksykograficznie najmniejszy ciąg.

Przykład

Przykład 1

3
2 -3 2

Wyjście 1

-3 -1 2

Uwagi

$[2,-3,2] \to [2, -1, 2] \to [-3, -1, 2]$

Podzadania

Dla $100\%$ danych wejściowych zachodzi $1\leq n\leq 10^5$ oraz $|a_i|\leq 10^9$.

Dla testów $1\sim 4$ zachodzi $n\leq 5$.

Dla testów $5\sim 7$ zachodzi $n\leq 10^3$.

Dla testów $8\sim 10$ brak dodatkowych ograniczeń.