# 游耕者（夜）

- 参考时间限制：1.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：256 MB

## 背景故事

游耕者还没有自己的农田，每天从住处附近的农场出发，依次到各处农场帮忙耕作，最后返回出发点。夜间为了避免迷路，只沿正东、正西、正南、正北方向行走。农场分布在广阔的地图上，需要规划一条消耗较小的巡回路线。

## 形式化问题描述

平面上有 $n$ 个农场，编号为 $1$ 到 $n$ ，农场 $i$ 的坐标为 $(x_i,y_i)$ .不同编号的农场可以位于同一坐标。

从农场 $i$ 到农场 $j$ 的代价为：

$$d(i,j)=|x_i-x_j|+|y_i-y_j|$$

在农场之间选择若干条双向连线，使所有农场连通。连线的端点必须是给定的农场，每条连线的代价按上述距离规则计算；连线交叉处不会新增连接点。设所选连线总代价的最小可能值为 $M$ .当 $n=1$ 时，约定 $M=0$ .

请构造一条从 $1$ 号农场出发、访问其他每个农场恰好一次并返回起点的路线。设路线总代价为 $C$ ，满足以下条件即为可接受的答案：

$$C\le 2.001M+0.001$$

访问次序以输出的农场编号为准，途经其他农场的坐标不会额外计为一次访问。无需输出 $C$ 或 $M$ ，也无需求出最短巡回路线。

## 输入格式

第一行一个整数 $n$ .

接下来 $n$ 行，第 $i$ 行两个整数 $x_i,y_i$ ，表示农场 $i$ 的坐标。

## 输出格式

输出一行 $n+1$ 个整数 $p_0,p_1,\ldots,p_n$ .

- 必须满足 $p_0=p_n=1$ .
- $p_0,p_1,\ldots,p_{n-1}$ 必须是 $1,2,\ldots,n$ 的一个排列。
- $C=\sum_{i=0}^{n-1}d(p_i,p_{i+1})$ 必须满足上述上界。
- 当 $n=1$ 时，输出 `1 1` .

本题采用特殊评测。输出任意满足要求的路线均可，不必与样例输出相同。

## 样例 1

### 输入

```text
3
5 3
1 7
7 7
```

### 输出

```text
1 3 2 1
```

### 解释

最小连接成本为 $M=12$ ，示例路线的总代价为 $C=20$ ，满足 $C\le2.001M+0.001$ .

## 样例 2

### 输入

```text
5
7 3
1 0
-5 3
7 9
9 10
```

### 输出

```text
1 4 5 2 3 1
```

### 解释

最小连接成本为 $M=27$ ，示例路线的总代价为 $C=48$ ，满足 $C\le2.001M+0.001$ .

## 样例 3

### 输入

```text
10
15 616
15 7
1 6794
13 245
1233 44
15 6
97 94
123 321
3020 100
456 987
```

### 输出

```text
1 4 8 7 2 6 5 9 10 3 1
```

### 解释

最小连接成本为 $M=10997$ ，示例路线的总代价为 $C=19986$ ，满足 $C\le2.001M+0.001$ .

## 样例 4

### 输入

```text
1
0 0
```

### 输出

```text
1 1
```

### 解释

只有一个农场，路线从该农场出发并直接结束，$M=C=0$ .

## 样例 5

### 输入

```text
4
0 0
0 0
3 4
3 4
```

### 输出

```text
1 2 3 4 1
```

### 解释

农场 $1,2$ 重合，农场 $3,4$ 重合，但各编号仍须访问。两处坐标之间的代价为 $7$ ，因此 $M=7$ ，示例路线的总代价为 $C=14$ .

## 数据范围与保证

- $1\le n\le400000$ .
- $-10000\le x_i,y_i\le10000$ ，所有坐标均为整数。
- 允许坐标重合、所有点共线或多个点共圆。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |