ESRC Training C/C++

Given a sequence of n integers a₁, a₂,... a_n. Sort it in descending order of absolute value (|a'¹| ≥ |a'²| ≥ ... ≥ |a'ⁿ|). Note that if two items have the same absolute value, the positive one comes first in the list.

Input

Line 1: contains the integer n (1 ≤ n ≤ 10³).

Line 2 to n + 1: (i + 1)-th line contains the integer a_i (|a_i| ≤ 10⁹)

Output

Line 1 to n: each line contains each item of the sequence in desired order.

Example

Input:
3
1
3
2

Output:
3
2
1