Bajtazar 今天过生日。有 $k$ 位客人来参加生日聚会。Bajtazar 期待着许多客人的到来，并准备了一个巨大的蛋糕。现在需要把它切开！

Bajtazar 有一个边长为 $10^6$ 的正方形桌子，他在上面建立了一个坐标系。桌子的左下角坐标为 $(0, 0)$，右上角坐标为 $(10^6, 10^6)$。随后，Bajtazar 把蛋糕放在了桌子上。蛋糕是一个顶点坐标为整数的简单多边形，且蛋糕的每一条边都平行于桌子的某一条边。

Bajtazar 将进行 $k$ 次切割，把蛋糕分成 $k+1$ 个（不一定连通的）面积相等的块。他切割的方式非常独特：他在桌子的左下角安装了一个功率很强的激光器。起初，激光器是关闭的，指向点 $(1, 0)$。随后，Bajtazar 将缓慢地逆时针旋转激光器。在此过程中，安装在激光器上的显示屏会显示激光所指向的方向。该点始终距离桌子左下角恰好 1 个单位长度。因此，旋转开始时激光指向点 $(1, 0)$，旋转 45 度后指向点 $(\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2})$，再旋转 45 度后指向点 $(0, 1)$。

在此过程中，Bajtazar 会开启激光 $k$ 次。激光开启极短的时间，并立即沿通过桌子左下角和激光当前指向点的直线切开蛋糕。每次开启激光后，都会切下一块（不一定连通的）蛋糕，下一位客人会将其放到自己的盘子里。经过 $k$ 次切割后，剩下的第 $k+1$ 块蛋糕将由 Bajtazar 自己享用。

然而，Bajtazar 遇到了一个问题：什么时候开启激光，才能让所有客人（以及他自己）得到的蛋糕一样多？请帮助他，并指出在显示屏显示哪些坐标时开启激光。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ ($4 \le n \le 300\,000, 2 \mid n, 1 \le k \le 300\,000$)，分别表示蛋糕的边数和客人的数量。蛋糕的顶点按顺时针或逆时针顺序编号为 $1$ 到 $n$。接下来的 $n$ 行描述了蛋糕的形状；第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 10^6$)，表示蛋糕第 $i$ 个顶点的坐标。

你可以假设蛋糕的每一条边都平行于坐标轴，且描述中每两条相邻的边都相互垂直。此外，描述蛋糕的多边形是一个简单多边形（即没有两个顶点位于同一点，且两条边仅在它们有公共顶点时才相交）。

输出格式

输出应包含 $k$ 行。第 $i$ 行应包含两个实数 $p_i$ 和 $q_i$ —— 第 $i$ 次切割时激光应指向的方向坐标 $(p_i, q_i)$。如果两个坐标与正确答案的误差不超过 $10^{-6}$，则答案被认为是正确的。数字应以小数点后至少 1 位且最多 20 位的格式输出；不允许使用科学计数法。

注意：建议在 C++ 中使用 long double 类型来表示结果。

样例

输入 1

6 3
2 2
9 2
9 4
4 4
4 9
2 9

输出 1

0.894427190999916 0.447213595499958
0.707106781186548 0.707106781186548
0.447213595499958 0.894427190999916

说明 1

样例的解释：所求坐标为 $(\frac{2\sqrt{5}}{5}, \frac{\sqrt{5}}{5}), (\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2}), (\frac{\sqrt{5}}{5}, \frac{2\sqrt{5}}{5})$，通过这些点的直线分别为 $y = \frac{1}{2}x, y = x, y = 2x$（见图）。每块蛋糕的面积等于 6 平方单位。

子任务