JOI 国决定开始电视广播。JOI 国有 $N$ 户人家。为了让所有这些家庭都能收看电视节目，需要建造广播塔。

JOI 国的国王决定建造 $K$ 座广播塔。如果将第 $i$ 座广播塔建在坐标 $(X_i, Y_i)$ 处，并将输出功率设置为 $E_i$，那么距离 $(X_i, Y_i)$ 在 $\sqrt{E_i}$ 以内的家庭就能收看电视节目（两点 $(a, b)$ 和 $(c, d)$ 之间的距离由 $\sqrt{(a-c)^2 + (b-d)^2}$ 给出）。但是，将广播塔的输出功率设置为 $E_i$ 会消耗 $E_i$ 的能量。我们希望在确保所有家庭都能收看电视节目的同时，尽可能减少 $K$ 座广播塔消耗的能量总和（以下简称为“消耗能量”）。广播塔可以建在有家庭的坐标上，也可以在同一坐标上建造两座。

给定 JOI 国各家庭的坐标以及 $K$，请输出广播塔的建造位置和输出功率设置。消耗能量越少，得分越高。

限制

$1 \le N \le 500$ $1 \le K \le 30$ $0 \le A_i, B_i \le 1\,000\,000$

输入格式

输入文件按以下格式给出：

• 第 1 行包含两个整数 $N, K$，以空格分隔，表示 JOI 国的家庭数量为 $N$，本次建造的广播塔数量为 $K$。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含两个整数 $A_i, B_i$，以空格分隔，表示第 $i$ 户家庭的坐标为 $(A_i, B_i)$。

可以假设不存在两户家庭位于同一坐标的情况。

输出格式

输出的第 $i$ 行（$1 \le i \le K$）应包含三个整数 $X_i, Y_i, E_i$（$0 \le X_i \le 1\,000\,000, 0 \le Y_i \le 1\,000\,000, 0 \le E_i \le 1\,000\,000\,000\,000 (= 10^{12})$），以空格分隔。

评分标准

对于每个输入数据，你的得分计算如下：

设所有参赛者提交的输出中，消耗能量的最小值为 $E_0$。如果你的输出不满足题目条件，得分为 0。如果满足条件，设你的输出消耗能量为 $E$，则：

• 当 $\frac{E}{E_0} > 1.5$ 时，得分为 0。
• 当 $\frac{E}{E_0} \le 1.5$ 时，得分为： $$\left( 4 \times \left( 1.5 - \frac{E}{E_0} \right)^2 \right) \times 20$$ 的值四舍五入到小数点后第一位。

样例

输入格式 1

10 3
0 300000
500000 800000
700000 200000
100000 500000
400000 900000
200000 1000000
300000 500000
300000 200000
500000 100000
1000000 0

输出格式 1

200000 700000 160000000000
300000 300000 90000000000
750000 0 62500000000

说明

该输入输出对应下图。每个圆表示从坐标 $(X_i, Y_i)$ 开始距离在 $\sqrt{E_i}$ 以内的范围。在这种情况下，消耗能量为 $160\,000\,000\,000 + 90\,000\,000\,000 + 62\,500\,000\,000 = 312\,500\,000\,000$（3125 亿）。