도로 건설

시간 제한10초메모리 제한2048 MB

요약

N개의 점이 주어질 때 모든 점 쌍의 맨해튼 거리 중 가장 작은 K개를 오름차순으로 출력한다. N과 K는 최대 250000이다.

난이도: 어려움10점 중 9점
유형: 분할 정복, 정렬, 힙, 기하
정답자: 아직 제출이 없습니다

문제

JOI 왕국에는 N개의 마을이 있다. 마을에는 1번부터 N번까지 번호가 붙어 있다. JOI 왕국의 영토는 xy평면으로 생각한다. 마을 i (1 ≤ i ≤ N)의 좌표는 (Xi, Yi)이다.

JOI 왕국에서는 마을을 잇는 K개의 도로를 건설할 계획을 세우고 있다. 마을 i와 마을 j (i ≠ j)를 잇는 도로를 건설하는 데 드는 비용은 |Xi − Xj| + |Yi − Yj|엔이다. "마을 i와 마을 j를 잇는 도로를 건설하는 것"과 "마을 j와 마을 i를 잇는 도로를 건설하는 것"은 같은 것으로 본다.

당신은 건설 사업을 맡았고, 비용을 추산하기 위해 몇몇 마을 쌍을 잇는 도로를 건설하는 데 드는 비용을 알고 싶다. 도로를 건설할 수 있는 N(N − 1)/2개의 마을 쌍 가운데 비용이 가장 싼 K개의 도로의 비용을 알고 싶다.

JOI 왕국의 마을 좌표와 K가 주어졌을 때, 비용이 가장 싼 K개의 도로의 비용을 계산하는 프로그램을 작성하라.

입력

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

N K
X1 Y1
.
.
.
XN YN

출력

표준 출력에 K개의 줄을 쓴다. k번째 줄 (1 ≤ k ≤ K)에는 k번째로 싼 도로의 비용을 출력한다.

제한

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).

예제4

예제 1
입력
```
3 2
-1 0
0 2
0 0
```
예상 출력
```
1
2
```
예제 2
입력
```
5 4
1 -1
2 0
-1 0
0 2
0 -2
```
예상 출력
```
2
2
3
3
```
예제 3
입력
```
4 6
0 0
1 0
3 0
4 0
```
예상 출력
```
1
1
2
3
3
4
```

예제 4

입력

예상 출력