21788번 - 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 ≤ i ≤ 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 , 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, in order to estimate the cost. Among the 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.

Read the following data from the standard input. Given values are all integers.

N K
X1 Y1
.
.
.
XN YN

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

• 2 ≤ N ≤ 250 000.
• 1 ≤ K ≤ min (250 000, N(N − 1)/2).
• −1 000 000 000 ≤ X_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• −1 000 000 000 ≤ Y_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• (X_i, Y_i) ≠ (X_j, Y_j) (1 ≤ i < j ≤ N).