Problem Description

There are $n$ spheres in the three-dimensional space, labeled by $1, 2, ... , n$. The center of the $i$-th sphere is at point $(x_i, y_i, z_i)$, and its radius is $r_i$.

Let us denote the distance between spheres $i$ and $j$ as

$$d(i,j) = max{\left(0, \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2 + (z_i-z_j)^2} - r_i - r_j\right)} $$

That means choosing two points $P$ and $Q$, where $P$ is inside or on the surface of sphere $i$ and $Q$ is inside or on the surface of sphere $j$, and minimizing the Euclidean distance between $P$ and $Q$.

There are $\frac{n(n−1)}{2}$ pairs $(i, j)$ such that $1 \le i < j \le n$. Please find the smallest $k$ values among the values of $d(i, j)$ for all these pairs.

Input

The first line of the input contains an integer $T (1 \le T \le 3)$, denoting the number of test cases.

Each test case starts with a single line containing two integers $n$ and $k$ $(2\le n\le 100000, 1\le k\le \min(300,\frac {n(n−1)} 2)$, denoting the number of spheres and the parameter $k$.

Each of the next $n$ lines contains four integers, $x_i$, $y_i$, $z_i$, and $r_i$, $(0 \le x_i, y_i, z_i \le 10^6, 1 \le r_i \le 10^6)$, describing $i$-th sphere.

Output

For each test case, print $k$ lines, each line containing a single integer: the smallest $k$ values among $d(i, j)$, in non-decreasing order. To avoid precision error, print the values of $\lceil d(i, j)\rceil$: the values of the respective $d(i, j)$ rounded up. For example, $\lceil5\rceil = 5$, and $\lceil5.1\rceil = 6$.

Sample

1
4 6
0 0 0 1
0 3 2 2
3 2 1 1
1 1 2 2

0
0
0
1
1
2