Given a sequence $a_1, a_2, \dots, a_n$, you can perform the following operation any number of times:

• Choose an index $i$ and replace $a_i$ with $-(a_1 + a_2 + \dots + a_n)$.

Find the lexicographically smallest sequence $a$ that can be obtained.

Input

The first line contains a positive integer $n$.

The next line contains $n$ integers, given in non-decreasing order, representing $a_i$.

Output

Output a single line containing $n$ integers, representing the lexicographically smallest sequence.

Examples

Input 1

3
2 -3 2

Output 1

-3 -1 2

Note 1

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

Subtasks

For $100\%$ of the data, $1 \leq n \leq 10^5$ and $|a_i| \leq 10^9$.

For test cases $1 \sim 4$, $n \leq 5$.

For test cases $5 \sim 7$, $n \leq 10^3$.

For test cases $8 \sim 10$, there are no additional constraints.