题目描述

平面上有 N 只羊，位置分别为给定的点。你需要放置 K 只牧羊犬（也看作平面点），使得每只羊到最近一只牧羊犬的距离之和尽量小。

换句话说，给定 N 个点，你需要再选择 K 个点，使得：

$$\sum_{i=1}^{N} \min_{1\le j\le K} dist(\text{sheep}_i, \text{hound}_j)$$

尽可能小。

请输出任意一组牧羊犬坐标。

输入格式

第一行输入两个正整数 N, K，分别表示羊的数量和牧羊犬数量。

接下来 N 行，每行两个整数 Xi, Yi，表示第 i 只羊的坐标。

输出格式

输出 K 对实数，表示牧羊犬的坐标，保留到小数点后 6 位。

允许某只牧羊犬与某只羊重合。

数据范围

• 1 <= K < N <= 1000
• 1 <= K <= 100
• 0 <= Xi,Yi <= 10000

评分方式

本题为近似优化题。对每个测试点，你的得分为：

$$\operatorname{round}\left(\min\left(1,\frac{author\_score}{your\_score}\right)^2 \cdot test\_score\right)$$

其中：

• author_score 为作者程序得到的目标函数值；
• your_score 为你的程序得到的目标函数值；
• test_score 为该测试点的满分。

样例

输入

7 2
1 2
1 4
2 5
3 2
4 4
5 6
6 5

输出

1.750000 3.250000
5.000000 5.000000

说明

不要求输出最优解，只要输出任意一组合法坐标即可。