시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 2048 MB 6 6 6 100.000%

문제

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 (Xi, Yi).

In JOI Kingdom, they are planning to construct K roads connecting towns. It costs |Xi − Xj| + |Yi − Yj| 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 ≤ 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).

서브태스크

번호 배점 제한
1 5

N ≤ 1 000.

2 6

Yi = 0 (1 ≤ i ≤ N).

3 7

K = 1.

4 20

K ≤ 10.

5 27

N ≤ 100 000.

6 35

No additional constraints.

예제 입력 1

3 2
-1 0
0 2
0 0

예제 출력 1

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 (3 × 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.

예제 입력 2

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

예제 출력 2

2
2
3
3

Since N = 5, there are (5 × 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.

예제 입력 3

4 6
0 0
1 0
3 0
4 0

예제 출력 3

1
1
2
3
3
4

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

예제 입력 4

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

예제 출력 4

3
3
4
5
6
6
6
7
7
7

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.