题目描述

题目译自 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$ 便宜的道路价格。

样例 1

输入

3 2 
-1 0 
0 2
0 0

输出

1
2

小城 $1, 2, 3$ 的坐标分别为 $(-1, 0), (0,2), (0,0)$，有 $\frac{3\times 2}{2}=3$ 种道路。

• 在小城 $1$ 和 $2$ 之间建设道路花费 $|(−1) − 0| + |0 − 2| = 3$ 元。
• 在小城 $1$ 和 $3$ 之间建设道路花费 $|(−1) − 0| + |0 − 0| = 1$ 元。
• 在小城 $2$ 和 $3$ 之间建设道路花费 $|0 − 0| + |2 − 0| = 2$ 元。

建设道路的价格从便宜到贵分别是 $1, 2, 3$。因此第一行输出 $1$，第二行输出 $2$。

本输入满足子任务 $1, 4, 5, 6$ 的条件。

样例 2

输入

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

输出

2
2
3
3

由 $N=5$ 知有 $\frac{5\times 4}{2}=10$ 种道路。

建设道路的价格从便宜到贵分别是 $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$。因此，前 $4$ 便宜的道路价格为 $2, 2, 3, 3$。

本输入满足子任务 $1, 4, 5, 6$ 的条件。

样例 3

输入

4 6
0 0
1 0
3 0
4 0

输出

1
1
2
3
3
4

本输入满足子任务 $1, 2, 4, 5, 6$ 的条件。

样例 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

本输入满足子任务 $1, 4, 5, 6$ 的条件。

数据范围与提示

对于 $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)$

各子任务详情如下：

子任务编号	分值	特殊限制
1	$5$	$N \le 10^3$
2	$6$	$Y_i = 0$
3	$7$	$K = 1$
4	$20$	$K \le 10$
5	$27$	$N \le 10^5$
6	$35$	无特殊限制