Vương quốc JOI có \(N\) thị trấn, đánh số từ \(1\) đến \(N\). Lãnh thổ được xem là mặt phẳng \(xy\). Thị trấn \(i\) (\(1\le i\le N\)) có tọa độ \((X_i,Y_i)\).

Vương quốc dự định xây \(K\) con đường nối các thị trấn. Chi phí xây một con đường nối thị trấn \(i\) và thị trấn \(j\) (\(i\ne j\)) là \(|X_i-X_j|+|Y_i-Y_j|\) yên. Việc xây đường nối \(i\) với \(j\) và việc xây đường nối \(j\) với \(i\) được xem là cùng một phương án.

Bạn phụ trách dự án và muốn biết chi phí của một số cặp thị trấn để ước tính ngân sách. Trong \(N(N-1)/2\) cặp thị trấn có thể nối bằng đường, bạn muốn biết chi phí của \(K\) con đường rẻ nhất.

Cho tọa độ các thị trấn và \(K\), hãy tính chi phí của \(K\) con đường rẻ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Mọi giá trị đều là số nguyên.

N K
X_1 Y_1
...
X_N Y_N

Dữ liệu ra

In \(K\) dòng. Dòng thứ \(k\) (\(1\le k\le K\)) chứa chi phí của con đường rẻ thứ \(k\).

Ràng buộc

• \(2\le N\le250000\).
• \(1\le K\le\min(250000,N(N-1)/2)\).
• \(-10^9\le X_i,Y_i\le10^9\) với mọi \(1\le i\le N\).
• \((X_i,Y_i)\ne(X_j,Y_j)\) với mọi \(1\le i<j\le N\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le1000\).
• Nhóm 2 (6 điểm): \(Y_i=0\) với mọi \(1\le i\le N\).
• Nhóm 3 (7 điểm): \(K=1\).
• Nhóm 4 (20 điểm): \(K\le10\).
• Nhóm 5 (27 điểm): \(N\le100000\).
• Nhóm 6 (35 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 2
-1 0
0 2
0 0

1
2

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

2
2
3
3

4 6
0 0
1 0
3 0
4 0

1
1
2
3
3
4

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

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 2. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.