JOI 王国坐落于一个 $xy$ 平面上，王国里有 $N$ 座小城，分别编号为 $1\dots 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$ 便宜的道路价格。

样例一

input

3 2 
-1 0 
0 2
0 0

output

1
2

explanation

小城 $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$ 的条件。

样例二

input

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

output

2
2
3
3

explanation

由 $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$ 的条件。

样例三

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

input

4 6
0 0
1 0
3 0
4 0

output

1
1
2
3
3
4

样例四

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

input

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

output

3
3
4
5
6
6
6
7
7
7

限制与约定

对于 $100\mathrm{\%}$ 的测试数据，有 $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)\ne (X_j,Y_j)(1\le i<j\le N)$。

各子任务详情如下：

时间限制：$\mathtt{\text{10s}}$

空间限制：$\mathtt{\text{2GB}}$

下载

样例数据下载