지지 여부

3차원 공간에 $n$개의 구가 있다. 구는 $1, 2, \ldots, n$번으로 번호가 매겨져 있다. $i$번 구의 중심은 $(x_i, y_i, z_i)$이고, 반지름은 $r_i$이다.

두 구 $i$와 $j$ 사이의 거리는 다음과 같이 정의한다.

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

즉, 구 $i$의 내부 또는 표면에 있는 점 $P$와 구 $j$의 내부 또는 표면에 있는 점 $Q$를 고를 때, $P$와 $Q$ 사이 유클리드 거리의 최솟값이 $d(i,j)$이다.

$1 \le i < j \le n$을 만족하는 쌍 $(i, j)$는 $\frac{n(n-1)}{2}$개이다. 이 모든 쌍에 대한 $d(i,j)$ 값 중 가장 작은 $k$개를 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 3$)가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $k$ ($2 \le n \le 100\,000$, $1 \le k \le \min\left(300, \frac{n(n-1)}{2}\right)$)가 주어진다.

이어지는 $n$개의 줄에는 $i$번째 구를 나타내는 네 정수 $x_i$, $y_i$, $z_i$, $r_i$ ($0 \le x_i, y_i, z_i \le 10^6$, $1 \le r_i \le 10^6$)가 주어진다.

각 테스트 케이스마다 $k$개의 줄을 출력한다. 각 줄에는 가장 작은 $k$개의 $d(i,j)$ 값을 오름차순으로 한 줄에 하나씩, 올림한 값 $\lceil d(i,j) \rceil$로 출력한다. 예를 들어 $\lceil 5 \rceil = 5$이고 $\lceil 5.1 \rceil = 6$이다.