Road Construction

Time limit10sMemory limit2048 MB

Summary

Given N points, output the K smallest Manhattan distances among all pairs, in increasing order, for N and K up to 250000.

Level: Hard9 of 10
Topics: Divide and conquer, Sorting, Heap, Geometry
Solved: No attempts yet

Problem

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 town i (1 ≤ i ≤ N) are (Xi, Yi).

JOI Kingdom plans to construct K roads connecting towns. It costs |Xi − Xj| + |Yi − Yj| yen to construct a road connecting town i and town j (i ≠ j). "Constructing a road connecting town i and town j" and "constructing a road connecting town j and town i" are considered the same.

You are in charge of the construction project, and you want to know the costs of constructing roads for some pairs of towns in order to estimate the cost. Among the N(N − 1)/2 pairs of towns for which a road can be constructed, you want to know the costs of the K cheapest roads.

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

Input

Read the following data from the standard input. All given values are integers.

N K
X1 Y1
.
.
.
XN YN

Output

Write K lines to the standard output. In the k-th line (1 ≤ k ≤ K), output the cost of the k-th cheapest road.

Constraints

2 ≤ N ≤ 250 000.
1 ≤ K ≤ min (250 000, N(N − 1)/2).
−1 000 000 000 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).
−1 000 000 000 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).
(Xi, Yi) ≠ (Xj, Yj) (1 ≤ i < j ≤ N).

Examples4

Example 1
Input
```
3 2
-1 0
0 2
0 0
```
Expected output
```
1
2
```
Example 2
Input
```
5 4
1 -1
2 0
-1 0
0 2
0 -2
```
Expected output
```
2
2
3
3
```
Example 3
Input
```
4 6
0 0
1 0
3 0
4 0
```
Expected output
```
1
1
2
3
3
4
```

Example 4

Input

Expected output