JOI 王国共有 $N$ 个城镇，城镇编号从 $1$ 到 $N$。JOI 王国的土地被视为 $xy$ 平面。城镇 $i$ ($1 \le i \le N$) 的坐标为 $(X_i, Y_i)$。

在 JOI 王国，他们计划修建 $K$ 条连接城镇的道路。修建连接城镇 $i$ 和城镇 $j$ ($i \neq j$) 的道路的费用为 $|X_i - X_j| + |Y_i - Y_j|$ 日元。注意，我们认为“修建连接城镇 $i$ 和城镇 $j$ 的道路”与“修建连接城镇 $j$ 和城镇 $i$ 的道路”是相同的。

由于你负责这项建设工程，为了估算成本，你需要知道修建连接某些城镇对的道路的费用。在所有 $\frac{N(N - 1)}{2}$ 对城镇中，你想要知道费用最低的 $K$ 条道路的费用。

编写一个程序，给定 JOI 王国各城镇的坐标和 $K$ 的值，计算费用最低的 $K$ 条道路的费用。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N \ K$ $X_1 \ Y_1$ $\vdots$ $X_N \ Y_N$

输出格式

向标准输出写入 $K$ 行。在第 $k$ 行 ($1 \le k \le K$)，输出费用第 $k$ 低的道路的费用。

数据范围

• $2 \le N \le 250\,000$
• $1 \le K \le \min \left( 250\,000, \frac{N(N - 1)}{2} \right)$
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $-1\,000\,000\,000 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $(X_i, Y_i) \neq (X_j, Y_j)$ ($1 \le i < j \le N$)

子任务

1. (5 分) $N \le 1\,000$
2. (6 分) $Y_i = 0$ ($1 \le i \le N$)
3. (7 分) $K = 1$
4. (20 分) $K \le 10$
5. (27 分) $N \le 100\,000$
6. (35 分) 无附加限制

样例

样例输入 1

3 2
-1 0
0 2
0 0

样例输出 1

1
2

说明 1

城镇 1 的坐标为 $(-1, 0)$，城镇 2 的坐标为 $(0, 2)$，城镇 3 的坐标为 $(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 行输出 1，第 2 行输出 2。

样例输入 2

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

样例输出 2

2
2
3
3

样例输入 3

4 6
0 0
1 0
3 0
4 0

样例输出 3

1
1
2
3
3
4

样例输入 4

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

样例输出 4

3
3
4
5
6
6
6
7
7
7