시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 512 MB 4 4 4 100.000%

문제

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)}\text{.}$

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.

입력

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 100 000, 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.

출력

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$.

예제 입력 1

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


예제 출력 1

0
0
0
1
1
2