Given $n$ integer points on a plane, the coordinates of the $i$-th ($1 \le i \le n$) point are $(x_i, y_i)$.

You need to sort all points according to $\text{atan2}(y_i, x_i)$, which means sorting them counter-clockwise starting from the negative $x$-axis (exclusive).

Note the following:

• $\text{atan2}(0, 0) = 0$
• $\text{atan2}(0, x) = \pi\;(\forall x < 0)$

If two points have the same polar angle, you may order them in any relative order.

Input

The first line of input contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The next line contains $n$ pairs of integers $x_i, y_i$ ($-10^{18} \le x_i, y_i \le 10^{18}$).

Output

Output a single line containing $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct), describing your sorting.

Subtasks

• Subtask 1 (10 points): $|x_i|, |y_i| \le 10^4$
• Subtask 2 (20 points): $|x_i|, |y_i| \le 10^9$
• Subtask 3 (70 points): No additional constraints.

Examples

Input 1

9
-1 0
0 0
0 -1
-1 -1
1 1
1 -1
-1 1
1 0
0 1

Output 1

4 3 6 2 8 5 9 7 1