Looking at things from a different angle, the world might be different. — Xiao Qiang

In a $k$-dimensional space, there are $n$ black points and $n$ white points. We determine a unique corresponding white point for each black point, resulting in $n!$ possible matching methods. We define the "moving distance" between these $n$ black points and $n$ white points as the minimum sum of the $n$ Euclidean distances between the corresponding black and white points across all possible matching methods.

For example, consider three black points $\{1, 5, 6\}$ and three white points $\{2, 3, 4\}$ in one-dimensional space. The moving distance between them is $|1-2| + |5-3| + |6-4| = 4$. You can verify that this is indeed the matching method that minimizes the sum of distances.

You are given $n$ black points and $n$ white points in three-dimensional space. You want to project them onto a $k$-dimensional subspace ($1 \le k \le 2$). A one-dimensional subspace is a line in three-dimensional space, and a two-dimensional subspace is a plane in three-dimensional space. The projection of a point onto a subspace is the point in that subspace closest to it. For example, after projecting the four points $(0, 0, 0)$, $(1, 1, 0)$, $(1, 0, 0)$, and $(0, 1, 0)$ onto the line $x - y = 0, z = 0$, the resulting projected points are $(0, 0, 0)$, $(1, 1, 0)$, $(0.5, 0.5, 0)$, and $(0.5, 0.5, 0)$.

You want to maximize the moving distance of these $n$ black points and $n$ white points after they are projected onto this $k$-dimensional subspace. Please calculate this maximum value divided by $n$.

Input

The input contains multiple test cases. Each test case is formatted as follows:

The first line contains two integers $n$ and $k$, representing the number of points and the dimension to project onto.

The following $2n$ lines each contain three numbers, representing the coordinates of the points.

The file ends with a line containing two numbers $-1 \ -1$.

Output

For each test case, output a single number (not exceeding 30 characters in length) representing the result.

Your answer is considered correct if the relative error between your answer and the reference answer does not exceed $10^{-7}$.

Only if the results for all test cases in a file are correct will you receive the score for that test file.

Examples

Input 1

2 1
0 0 0
1 1 0
0 1 0
1 0 0
-1 -1

Output 1

0.70710678118655

Input 2

4 2
0 0 0
0 1 1
1 0 1
1 1 0
0 0 1
0 1 0
1 0 0
1 1 1
-1 -1

Output 2

0.73883404559321

Note

See projection/projection3.in and projection/projection3.ans in the contestant directory for Example 3.

Constraints

• For 30% of the data, $k = 1$, $n \le 1000$, and the $z$-coordinate of all points is $0$. Each file contains at most one test case.
• For another 40% of the data, $k = 1$, $n \le 1000$, and all point coordinates are generated independently and uniformly at random in $[-1, 1]$. Each file contains at most ten test cases.
• For the remaining 30% of the data, $k = 2$, $n \le 20$, and all point coordinates are generated independently and uniformly at random in $[-1, 1]$. Each file contains at most ten test cases.
• For 100% of the data, the coordinates of the points are in the range $[-1, 1]$, and the answer is at least $0.01$.