Problem Description

JOI Kingdom is a two-dimensional plane of size $x \times y$. There are $n$ towns in the kingdom, numbered from $1$ to $n$, where the $i$-th town is located at coordinates $(x_i, y_i)$.

JOI Kingdom is planning to build roads connecting pairs of towns. There are $k$ roads to be constructed. The cost to connect two different towns $a$ and $b$ is $|x_a - x_b| + |y_a - y_b|$ yen. Note that connecting towns $c$ and $d$ is considered the same as connecting towns $d$ and $c$, so constructing both is unnecessary and not allowed.

You are in charge of this road construction project. To calculate the costs, you need to determine the costs of the cheapest $k$ roads among the $\frac{n \cdot (n-1)}{2}$ possible roads.

Given the coordinates of the towns and the value of $k$, calculate the costs of the cheapest $k$ roads.

Input Format

The input consists of $n+1$ lines.

The first line contains two positive integers $n$ and $k$, where $n$ is the number of towns and $k$ is as described in the problem statement.

The next $n$ lines each contain two positive integers $x_i$ and $y_i$, representing the coordinates of the $i$-th town, where $1 \le i \le n$.

Output Format

The output consists of $k$ lines.

Each line contains an integer representing the cost of the $k$-th cheapest road.

Sample Input and Output

Sample Input #1

3 2
-1 0
0 2
0 0

Sample Output #1

1
2

Sample Input #2

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

Sample Output #2

2
2
3
3

Sample Input #3

4 6
0 0
1 0
3 0
4 0

Sample Output #3

1
1
2
3
3
4

Sample Input #4

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

Sample Output #4

3
3
4
5
6
6
6
7
7
7

Notes

Sample #1 Explanation

There are $\frac{3 \times 2}{2} = 3$ possible roads.

• 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 these costs gives $1, 2, 3$, so the output is $1$ and $2$.

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

Data Range and Constraints

This problem uses a Subtask scoring system.

Note: Slashes indicate no special restrictions.

For $100\%$ of the data:
- $2 \le n \le 2.5 \times 10^5$;
- $1 \le k \le \min(2.5 \times 10^5, \frac{n \cdot (n-1)}{2})$;
- $-10^9 \le x_i, y_i \le 10^9$ for $1 \le i \le n$;
- $(x_i, y_i) \neq (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 - Competition 2 - Japanese Problem Statement.

见题面 Input 部分

见题面 Output 部分