AT_abc448_f.[ABC448F] Authentic Traveling Salesman Problem

在一个二维平面上有编号为 $1$ 至 $N$ 的 $N$ 个点。点 $i$ 位于坐标 $(X_i, Y_i)$ 。

你将从点 $1$ 出发，每个位置正好访问一次，然后返回点 $1$ 。

从点 $i$ 移动到点 $j$ 需要 $\vert X_i - X_j \vert + \vert Y_i - Y_j \vert$ 秒。

输出一条从点 $1$ 出发，在 $10^{10}$ 秒内到达所有位置并返回点 $1$ 的路径。保证在给定的数据范围下至少存在一条这样的路线。

输入格式如下：

$N$

$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

设 $p_i (1 \leq i \leq N)$ 为访问过的 $i$ 个位置，并按以下格式输出答案。

$p_1$ $p_2$ $\dots$ $p_N$

如果满足以下所有条件，则认为您的答案是正确的。

• $(p_1, p_2, \dots, p_N)$ 是 $(1, 2, \dots, N)$ 的排列。
• $p_1 = 1$
• 设 $d(i, j)$ 为从位置 $i$ 移动到位置 $j$ 所需的秒数, $\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1} ) \leq 10^{10}$。

如果有多个正确答案，输出任意一个即可。

数据范围

• $1 \leq N \leq 6 \times 10^4$；
• $0 \leq X_i \leq 2 \times 10^7$；
• $0 \leq Y_i \leq 2 \times 10^7$；
• 如果 $i \neq j$，那么 $(X_i, Y_i) \neq (X_j, Y_j)$；
• 所有输入值均为整数。

样例解释 #1

$\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10$ ，因此输出满足条件。