题面描述

题目译自 JOISC 2021 Day2 T2「道路の建設案 / Road Construction」

JOI 王国坐落于一个 $xy$ 平面上，王国里有 $N$ 座小城，分别编号为 $1\ldots N$，其中第 $i$ 个小城的坐标为 $(X_i, Y_i)$。

现在王国正筹划着在小城之间建 $K$ 条路，而连接两个不同的小城 $i$ 和 $j$ 将花费 $|X_i-X_j|+|Y_i-Y_j|$ 元。在这里我们认为「连接小城 $i$ 和 $j$」和「连接小城 $j$ 和 $i$」本质相同。

和往常一样，你成为了这个项目的主管。为了估算花费情况，你想了解连接一些小城所需的花费。在这 $\frac{N(N-1)}{2}$ 条可能的道路中，你想了解最便宜的 $K$ 条道路的花费。

你的任务是，给出小城的坐标以及 $K$ 值，编写一个程序计算最便宜的 $K$ 条道路的花费。

输入格式

第一行两个整数 $N$, $K$。

接下来 $N$ 行每行两个整数 $X_i,~Y_i$。

输出格式

输出 $K$ 行，第 $k$ 行为第 $k$ 便宜的道路价格。

3 2 
-1 0 
0 2
0 0

1
2

5 4
1 -1
2 0
-1 0
0 2
0 -2

2
2
3
3

4 6
0 0
1 0
3 0
4 0

1
1
2
3
3
4

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

3
3
4
5
6
6
6
7
7
7

数据范围与提示

对于 $100\%$ 的测试数据，有 $2\le N\le 250000,~$$1\le K\le\min(250000, \frac{N(N-1)}{2}),~$$-10^9\le X_i,~Y_i\le 10^9,~$$(X_i,~Y_i)\neq (X_j,Y_j) (1\le i < j\le N)$。

各子任务详情如下：