Background

10s, 2048M.

Problem Description

The Kingdom of JOI is a $x \times y$ two-dimensional plane. There are $n$ towns in the kingdom, numbered $1, 2, \cdots, n$, and the coordinates of town $i$ are $(x_i, y_i)$.

In the Kingdom of JOI, there is a plan to build roads connecting two towns (hereinafter referred to as a “road construction project”). There will be $k$ roads. Connecting two different towns $a$ and $b$ costs $|x_a − x_b| + |y_a − y_b|$ yen. If there is already a road connecting $c$ and $d$, then there is no need and it is not allowed to build another road connecting $d$ and $c$, because they are the same.

You need to manage this “road construction project”. To calculate the costs, you need to figure out the costs required to connect some towns. Among these $\dfrac{n\cdot(n-1)}{2}$ possible roads, you want to know the costs of the cheapest $k$ roads.

Given the coordinates of the towns and $k$, compute how much money is needed for the cheapest $k$ roads.

Input Format

The input consists of $n+1$ lines.

The first line contains two positive integers $n, k$. $n$ is the number of towns, and the meaning of $k$ is described in the Description section.

Each of the next lines $2 \sim n+1$ contains two integers $x_i$ and $y_i$ ($1 \le i \le n$), representing the coordinates of town $i$.

Output Format

Output $k$ lines.

On line $k$, output one integer representing the cost in yen of the $k$-th cheapest road.

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

Hint

Sample #1 Explanation

There are $\dfrac{3 \times 2}{2} = 3$ possible choices.

• Town $1 \to$ town $2$: $|(-1)-0|+|0-2| = 3$ yen.
• Town $1 \to$ town $3$: $|(-1)-0|+|0-0| = 1$ yen.
• Town $2 \to$ town $3$: $|0-0|+|2-0| = 2$ yen.

Sorting them gives $1, 2, 3$, so the output is $1$ and $2$.

This sample satisfies Subtasks $1, 4, 5, 6$.

Sample #2 Explanation

There are $\dfrac{5 \times 4}{2} = 10$ possible choices.

After sorting, the costs are $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$.

This sample satisfies Subtasks $1, 4, 5, 6$.

Sample #3 Explanation

This sample satisfies Subtasks $1, 2, 4, 5, 6$.

Sample #4 Explanation

This sample satisfies Subtasks $1, 4, 5, 6$.

Constraints and Notes

This problem uses subtask scoring.

Note: A slash means there is no special restriction.

For $100\%$ of the testdata:

• $2 \le n \le 2.5 \times 10^5$.
• $1 \le k \le \min(2.5 \times 10^5,\ \dfrac{n\cdot(n-1)}{2}$).
• $-10^9 \le x_i, y_i \le 10^9$, and $1 \le i \le n$.
• $(x_i, y_i)\not = (x_j, y_j)$ for $1 \le i < j \le n$.

Notes

This problem is translated from The 20th Japanese Olympiad in Informatics 2020/2021 Spring Training Camp - Contest 2 - T2 Japanese statement.

Translated by ChatGPT 5