Problem Description

There are $n$ spheres in 3D-space, labeled by $1,2,\dots,n$. The $i$-th sphere's center is at $(x_i,y_i,z_i)$, and the radius of it is $r_i$.

Let's denote the distance between the $i$-th sphere and the $j$-th sphere $d(i,j)$ as

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

That means choosing two points $P$ and $Q$, where $P$ is on the $i$-th sphere's surface or inside it, $Q$ is on the $j$-th sphere's surface or inside it, and minimize the Euclidean distance bewteen $P$ and $Q$.

There are $\frac{n(n-1)}{2}$ pairs of $i,j(1\leq i<j\leq n)$, please find the $k$-th smallest values among these $d(i,j)$.

Input

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

In each test case, there are two integers $n,k(2\leq n\leq 100000,1\leq k\leq\min(300,\frac{n(n-1)}{2}))$ in the first line, denoting the number of spheres and the parameter $k$.

For the next $n$ lines, each line contains four integers $x_i,y_i,z_i,r_i(0\leq x_i,y_i,z_i\leq 10^6,1\leq r_i\leq 10^6)$, denoting each sphere.

Output

For each test case, print $k$ lines, each line contains an integer, denoting the $k$-th smallest values among these $d(i,j)$. You should print them in non-decreasing order. To avoid precision error, print $\lceil d(i,j)\rceil$ instead. For example, $\lceil 5\rceil=5$, and $\lceil 5.1\rceil=6$.

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