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

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 15\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 5000\).
• Cách tính điểm: Với mỗi test, gọi tổng khoảng cách theo phương án của giám khảo là \(res\), gọi tổng khoảng cách theo phương án của thí sinh là \(ans\), điểm số tính theo công thức sau: \(min(1,(\frac{res}{ans}))^2\).

Example

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

0.5 0.5
9 9