시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 512 MB66221129.730%

## 문제

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