题目描述

烧烤大师 Kosta 在曼哈顿开了 $N$ 家餐厅，按照 $1$ 到 $N$ 的数字进行标记，每个餐厅的位置都可以按照坐标轴上的点进行表示，比如餐厅 $A$ 标记为 $(X_A,Y_A)$。同时两个餐厅 $A,B$ 的距离为$|X_A-X_B|+|Y_A-Y_B|$。

Kosta 计划最多购买两台用于自动制作汉堡的现代化机器。每台机器都将安装在现有的餐厅中，对于所有其他餐厅，汉堡都是从安装机器的最近餐厅送来的。

我们定义 $D_C$ 表示从餐厅 $C$ 到安装机器的餐厅的最小距离。Kosta 希望 $D_C$ 的最大值最小。

编写一个程序，根据餐厅的位置和 Kosta 将购买的机器数量（一台或两台），计算 $D_C$ 的最低可能值。此外，你应确定机器的最佳位置。如果 Kosta 购买了两台机器，可以在同一家餐厅安装两台机器。

输入格式

第一行为一个整数 $K(1\le K\le 2)$，表示购买机器的数量。

第二行为一个整数 $N$，表示餐厅的数量。在接下来的 $N$ 行中，每行给出 $(X_K,Y_K)$ 表示餐厅坐标 $(0\le X_K,Y_K \le 10^6)$，餐厅的坐标互不相同。

输出格式

在第一行中，一个整数 $D$。

在第二行中，输出 $K$ 个自然数，表示要装电器的餐厅。

注意：解决方案不必是唯一的。

2
5
1 1
2 3
5 10
4 6
7 12

5
1 3 

2
10
3 6
1 4
4 1
4 7
4 10
3 8
3 10
6 7
5 1
2 10

5
1 3 

1
10
3 10
6 1
5 7
0 4
2 7
2 0
9 2
4 1
3 6
1 4

10
3

提示

若 $D$ 正确，但是第二行答案错误，你可以获得 $60 \%$ 的分数。

• Subtask $1$（$4$ pts）： $K=1,1\le N\le 1000$。
• Subtask $2$（$16$ pts）：$K=1,1000< N\le 200000$。
• Subtask $3$（$4$ pts）： $K=2,3\le N\le 100$。
• Subtask $4$（$24$ pts）：$K=2,100\le N\le 3000$。
• Subtask $5$（$52$ pts）：$K=2,3000< N\le 50000$。