平面上有 n 个点 (xi, yi),其整数坐标在 0 到 106 之间。编号为 a 和 b 的两点之间的距离被称为以下值:$$\operatorname{dist}(a,b)=|x_{a}-x_{b}|+|y_{a}-y_{b}|$$(通过该公式计算的距离称为曼哈顿距离)。
我们将哈密顿路径称为从 1 到 n 的数字的某种排列 pi。我们说这条路径的长度是值$$\sum_{i=1}^{n-1} \text{dist}(p_i, p_{i+1})$$。
找到一些长度不超过 25 × 108 的哈密顿路径。请注意,您不必最小化路径长度。
输入
第一行包含整数 n (1 ≤ n ≤ 106)。
第 i + 1 行包含第 i 个点的坐标:xi 和 yi (0 ≤ xi, yi ≤ 106)。
保证没有两点重合。
输出
打印数字 pi 从 1 到 n 的排列 — 寻找的哈密顿路径。排列必须满足不等式 $${ \sum _ { i = 1 } ^ { n - 1 } \operatorname { d i s t } ( p _ { i }, p _ { i + 1 } ) } \leq 2 5 \times 1 0 ^ { 8 }$$。
如果有多个可能的答案,请打印其中任何一个。
保证答案存在。
示例
输入 #1
5 0 7 8 10 3 4 5 0 9 12
输出 #1
4 3 1 2 5
注意
在样本测试中,总距离为:
$$\text{dist}(4,3)+\text{dist}(3,1)+\text{dist}(1,2)+\text{dist}(2,5)=$$
(|5 - 3| + |0 - 4|) + (|3 - 0| + |4 - 7|) + (|0 - 8| + |7 - 10|) + (|8 - 9| + |10 - 12|) = 2 + 4 + 3 + 3 + 8 + 3 + 1 + 2 = 26