We call any sequence of points in the plane a plot. We intend to replace a given plot $(P_{1},\ldots,P_{n})$ with another that will have at most $m$ points ($m ≤ n$) in such a way that it "resembles" the original plot best.

The new plot is created as follows. The sequence of points P_{1},…,P_{n} can be partitioned into $s$ ($s ≤ m$) contiguous subsequences:

$$(P_{ko+1},…,P_k1), (P_{k1+1},…,P_k2), …, (P_{k(s-1)+1},…,P_ks)$$

where $0 = k_{0} < k_{1} < k_{2} < … < k_{s} = n$, and afterwards each subsequence $(P_{k(i-1)+1},\ldots,P_{ki})$, for $i=1,\ldots,s$, is replaced by a new point $Q_{i}$. In that case we say that each of the points $P_{k(i-1)+1},\ldots,P_{ki }$ has been contracted to the point $Q_{i}$. As a result a new plot, represented by the points $Q_{1},\ldots,Q_{s}$, is created. The measure of such plot's resemblance to the original is the maximum distance of all the points $P_{1},\ldots,P_{n}$ to the point it has been contracted to:

$$\max_{i=1,\ldots,s} {\left(\max_{j=k_{i-1}+1,...,k_i} {(d(P_j,Q_i))}\right)}$$

where $d(P_{j},Q_{i})$ denotes the distance between $P_{j}$ and $Q_{i}$, given by the well-known formula:

$$d((x_1,y_1),(x_2,y_2)) = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$$

An exemplary plot $(P_{1},\ldots,P_{7})$ and the new plot $(Q_{1},Q_{2})$, where $(P_{1},\ldots,P_{4})$ are contracted to $Q_{1}$, whereas $(P_{5},P_{6},P_{7})$ to $Q_{2}$.

For a given plot consisting of $n$ points, you are to find the plot that resembles it most while having at most m points, where the partitioning into contiguous subsequences is arbitrary. Due to limited precision of floating point operations, a result is deemed correct if its resemblance to the given plot is larger than the optimum resemblance by at most 0.000001.

Input Format

In the first line of the standard input there are two integers $n$ and $m$, $1 ≤ m ≤ n ≤ 100\,000$, separated by a single space. Each of the following n lines holds two integers, separated by a single space. The $(i+1)$-th line gives $x_{i}$, $y_{i}$, $-1\,000\,000 ≤ x_{i},y_{i} ≤ 1\,000\,000$, denoting the coordinates $(x_{i},y_{i})$ of the point $P_{i}$.

Output Format

In the first line of the standard output one real number d should be printed out, the resemblance measure of the plot found to the original one. In the second line of the standard output there should be another integer $s$, $1 ≤ s ≤ m$. Next, the following s lines should specify the coordinates of the points $Q_{1},\ldots,Q_{s}$, one point per line. Thus the $(i+2)$-th line should give two real numbers $u_{i}$ and $v_{i}$, separated by a single space, that denote the coordinates $(u_{i},v_{i})$ of the point $Q_{i}$. All the real numbers should be printed with at most 15 digits after the decimal point.

Example

Input

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

Output

3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199