Description

Original problem from JOISC 2021 Day2 T2 Road Construction.

There are N towns in JOI Kingdom. The towns are numbered from $1$ to $N$. The land of JOI Kingdom is considered as the $xy$-plane. The coordinates of the town $i$ $(1 \leq i \leq N)$ is $(X_i, Y_i)$.

In JOI Kingdom, they are planning to construct K roads connecting towns. It costs $|X_i − X_j| + |Y_i − Y_j|$ yen to construct a road connecting the town $i$ and the town $j~(i \neq j)$. Note that we consider “the construction of a road connecting the town $i$ and the town $j$” and “the construction of a road connecting the town $j$ and the town $i$” to be the same.

Since you are in charge of the construction project, you want to know the cost to construct roads connecting some pairs of towns to construct roads, in order to estimate the cost. Among the $\frac{N(N − 1)}{ 2 }$ pairs of towns to construct roads, you want to know the costs of the K cheapest roads.

Write a program which, given the coordinates of the towns of JOI Kingdom and the value of $K$, calculates the costs of the $K$ cheapest roads.

Input Format

In the first line, there are two integers $N$ and $K$.

In the following $N$ lines, there are two integers $X_i$ and $Y_i$ each line.

Output Format

Output $k$ lines. In the $k$-th line ($1 \leq k \leq K)$, output the cost of the $k$-th cheapest road.

Sample 1

3 2 
-1 0 
0 2
0 0

1
2

The coordinates of the town $1$ is $(−1, 0)$, the coordinates of the town $2$ is $(0, 2)$, and the coordinates of the town $3$ is $(0, 0)$.

There are $\frac{3\times 2}{2}=3$ pairs of towns.

• It costs $|(−1) − 0| + |0 − 2| = 3$ yen to construct a road connecting the town $1$ and the town $2$.
• It costs $|(−1) − 0| + |0 − 0| = 1$ yen to construct a road connecting the town $1$ and the town $3$.
• It costs $|0 − 0| + |2 − 0| = 2$ yen to construct a road connecting the town $2$ and the town $3$.

The costs of the roads are $1, 2, 3$ from the cheapest. Therefore, output $1$ to the $1$-st line, and output $2$ to the $2$-nd line. This sample input satisfies the constraints of Subtasks $1, 4, 5, 6$.

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

2
2
3
3

Since $N=5$, there are $\frac{5\times 4}{2}=10$ pairs of towns.

The costs of the roads are $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$ from the cheapest. Therefore, the costs of the $4$ cheapest roads are $2, 2, 3, 3$.

This sample input satisfies the constraints of Subtasks $1, 4, 5, 6$.

4 6
0 0
1 0
3 0
4 0

1
1
2
3
3
4

This sample input satisfies the constraints of Subtasks $1, 2, 4, 5, 6$.

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

This sample input satisfies the constraints of Subtasks $1, 4, 5, 6$.

Constraints

For all test data, it is guaranteed that $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)$