给定平面上的 $n$ 个整点，第 $i$ ($1 \le i \le n$) 个点的坐标为 $(x_i, y_i)$。

你需要将所有点按照 $\text{atan2}(y_i, x_i)$ 进行排序，也即从 $x$ 轴负半轴（不含）开始进行逆时针排序。

你需要注意的是：

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

如果两个点的极角相同，你可以将极角相同的点按照任意顺序排序。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。

接下来一行，包含 $n$ 个整数 $x_i$, $y_i$ ($-10^{18} \le x_i, y_i \le 10^{18}$)。

输出格式

输出包含一行 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, $p_i$ 互不相同)，描述你的排序。

样例数据

样例输入

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

样例输出

4 3 6 2 8 5 9 7 1

子任务

• 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.