Stably sort integers by increasing absolute value.

Input

The first line contains \(n\). The second line contains \(n\) integers.

The input satisfies:

• \(0 <= n <= 1000\)

Output

Print the sorted values separated by spaces. Values with equal absolute value retain their input order.

Example

Input

5
-5 3 -2 1 2

Output

1 -2 2 3 -5