Bitocja 是一个拥有 $n$ 座城市的巨大国家，城市编号从 $1$ 到 $n$。Bitocja 位于笛卡尔坐标平面上。第 $i$ 座城市的坐标为 $(x_i, y_i)$，且不存在两座城市位于同一坐标点。

城市数量众多固然意味着国家强大且管理有方，但并非所有人都对此感到满意。新当选的 Bitomir 总理负责规划传统的节日游行，游行需要访问所有城市并回到起点。然而，Bitomir 的民众支持率并不如他所愿——如果他选择的城市访问顺序不能使游行路线达到最优（即最短）长度，公民们就会抱怨浪费公共资金。而寻找这样一条最优路线（通常称为旅行商问题，属于所谓的 NP-难问题）需要巨大的计算能力，因此当 Bitocja 国王得知所需计算机的数量和成本后，他很快同意缩减今年游行的规模。

最终决定游行只访问 $n$ 座城市中的 $k$ 座。Bitomir 可以自由选择城市（他可以告诉公民这些是文化和历史最丰富的城市），但他必须在选定的城市中提出一个最优的访问顺序，即总路线长度必须在 $k!$ 种可能性中最小。

你能帮助 Bitomir 吗？形式化地说，你需要从给定的 $n$ 个点中选择 $k$ 个点，并按某种顺序输出。设你的路线总长度为 $A$。如果检查程序发现你输出的点的顺序使得总长度小于 $A \cdot (1 - 10^{-9})$，你将获得该测试点的“错误答案”判决。由城市 $P_1, P_2, \dots, P_k$ 组成的路线总长度定义为 $k$ 段欧几里得距离之和： $$d(P_1, P_2) + d(P_2, P_3) + \dots + d(P_{k-1}, P_k) + d(P_k, P_1)$$ 其中点 $P_a(x_a, y_a)$ 和 $P_b(x_b, y_b)$ 之间的欧几里得距离为： $$d(P_a, P_b) = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}$$ 如果三座城市位于同一直线上，且两座城市之间的路线恰好经过第三座城市，不必担心——游行队伍只需利用 Bitocja 众多的桥梁和立交桥绕过它即可。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($n = 300\,000, k = 500$)，分别表示 Bajtocja 的城市总数和游行需要经过的城市数量。注意：题目中的样例测试不满足这些条件，且系统测试中不包含该样例（提交的解决方案不会在该样例上运行）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($-10^8 \le x_i, y_i \le 10^8$)，表示第 $i$ 座城市的坐标。对于 $i \neq j$，满足 $x_i \neq x_j$ 或 $y_i \neq y_j$。

输出格式

输出 $k$ 行，每行包含两个整数 $x_i, y_i$，用空格分隔，表示游行路线上依次访问的城市坐标。任何城市不得重复。输出任意一个正确解即可。

样例

输入 1

6 4
-10 -10
-10 10
10 -10
50 10
10 10
48 10

输出 1

-10 10
48 10
50 10
-10 -10

说明 1

输出的 $k = 4$ 座城市产生的总长度为： $$\sqrt{58^2 + 0^2} + \sqrt{2^2 + 0^2} + \sqrt{60^2 + 20^2} + \sqrt{0^2 + 20^2} \approx 143.246$$ 这四座城市的任何访问顺序都不会产生更小的总长度，因此输出是正确解之一。提醒：此样例测试不包含在 SIO 的测试用例中。