我们将平面上的一系列点称为一个“绘图”（plot）。我们打算将给定的绘图 $(P_{1},\ldots,P_{n})$ 替换为另一个至多包含 $m$ 个点（$m \le n$）的绘图，使得它能最好地“近似”原始绘图。

新绘图的创建方式如下：将点序列 $P_{1},\ldots,P_{n}$ 分割为 $s$ ($s \le m$) 个连续的子序列：

$$(P_{k_{0}+1},\ldots,P_{k_{1}}), (P_{k_{1}+1},\ldots,P_{k_{2}}), \ldots, (P_{k_{s-1}+1},\ldots,P_{k_{s}})$$

其中 $0 = k_{0} < k_{1} < k_{2} < \ldots < k_{s} = n$。随后，对于每个 $i=1,\ldots,s$，将子序列 $(P_{k_{i-1}+1},\ldots,P_{k_{i}})$ 替换为一个新点 $Q_{i}$。在这种情况下，我们称点 $P_{k_{i-1}+1},\ldots,P_{k_{i}}$ 被收缩到了点 $Q_{i}$。最终得到由点 $Q_{1},\ldots,Q_{s}$ 组成的新绘图。该绘图与原始绘图的相似度衡量标准是所有点 $P_{1},\ldots,P_{n}$ 到其被收缩到的点之间的最大距离：

$$\max_{i=1,\ldots,s} {\left(\max_{j=k_{i-1}+1,\ldots,k_{i}} {(d(P_{j},Q_{i}))}\right)}$$

其中 $d(P_{j},Q_{i})$ 表示点 $P_{j}$ 和 $Q_{i}$ 之间的距离，由以下公式给出：

$$d((x_{1},y_{1}),(x_{2},y_{2})) = \sqrt{(x_{2}-x_{1})^2+(y_{2}-y_{1})^2}$$

一个示例绘图 $(P_{1},\ldots,P_{7})$ 和新绘图 $(Q_{1},Q_{2})$，其中 $(P_{1},\ldots,P_{4})$ 被收缩到 $Q_{1}$，而 $(P_{5},P_{6},P_{7})$ 被收缩到 $Q_{2}$。

对于给定的包含 $n$ 个点的绘图，你需要找到一个至多包含 $m$ 个点的绘图，使其与原始绘图的相似度最高，其中分割成连续子序列的方式可以任意选择。由于浮点运算的精度限制，如果结果与最优相似度的偏差不超过 $0.000001$，则认为该结果是正确的。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$，$1 \le m \le n \le 100\,000$，由一个空格分隔。接下来的 $n$ 行，每行包含两个整数，由一个空格分隔。第 $(i+1)$ 行给出 $x_{i}, y_{i}$，$-1\,000\,000 \le x_{i},y_{i} \le 1\,000\,000$，表示点 $P_{i}$ 的坐标 $(x_{i},y_{i})$。

输出格式

第一行输出一个实数 $d$，表示所求绘图与原始绘图的相似度衡量值。第二行输出一个整数 $s$，$1 \le s \le m$。接下来的 $s$ 行应指定点 $Q_{1},\ldots,Q_{s}$ 的坐标，每行一个点。即第 $(i+2)$ 行应给出两个实数 $u_{i}$ 和 $v_{i}$，由一个空格分隔，表示点 $Q_{i}$ 的坐标 $(u_{i},v_{i})$。所有实数应保留小数点后最多 15 位。

样例

输入 1

7 2
2 0
0 4
4 4
4 2
8 2
11 3
14 2

输出 1

3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199