Siêu thị (Bài 3 bảng C1)

Có \(n\) khu vực dân cư, khu vực \(i\) ở vị trí (\(x_i, y_i\)). Người ta muốn đặt \(k\) siêu thị để cung cấp hàng hóa cho \(n\) khu vực dân cư này. Người dân ở khu vực dân cư \(i\) khi mua hàng sẽ chọn siêu thị gần nhất, do đó tiêu chí đánh giá việc đặt \(k\) siêu thị dựa trên giá trị: tổng các khoảng cách của từng khu vực dân cư đến siêu thị gần nhất, giá trị này càng nhỏ càng thể hiện việc chọn là tối ưu.

Yêu cầu: Cho \(n, k\) và tọa độ của \(n\) khu dân cư. Hãy xác định vị trí đặt \(k\) siêu thị để tổng các khoảng cách của từng khu vực dân cư đến siêu thị gần nhất càng nhỏ càng tốt.

Input

• Dòng đầu chứa hai số nguyên \(n,k\ (k \le n)\);
• \(n\) dòng sau, mồi dòng chứa hai số thực \(x_i,y_i\) (\(0 \le x_i,y_i \le 10000\)).

Output

• Ghi ra gồm \(k\) dòng, mỗi dòng chứa 2 số thực là tọa độ của các siêu thị

Cách tính điểm: Với mỗi test điểm số tính theo công thức dưới đây: \(min\left( 1,\left( \frac{\text{tổng khoảng cách theo phương án của giám khảo}}{\text{tổng khoảng cách theo theo phương án của thí sinh}} \right) \right)^2\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 15\);
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 1000\).

Example

5 2
0 0
1 0
1 1
0 1
9 9 

0.5 0.5
9 9