在三维空间中有 $n$ 个球体，编号为 $1, 2, \dots, 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$ 之间的欧几里得距离。

共有 $\frac{n(n-1)}{2}$ 对 $(i, j)$ 满足 $1 \le i < j \le n$。请在所有这些对的 $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)$) 的一行开始，分别表示球体的数量和参数 $k$。

接下来的 $n$ 行，每行包含四个整数 $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$)，描述第 $i$ 个球体。

输出格式

对于每个测试用例，输出 $k$ 行，每行包含一个整数：按非递减顺序排列的前 $k$ 个最小的 $d(i, j)$ 值。为了避免精度误差，请输出 $\lceil d(i, j) \rceil$ 的值，即对相应的 $d(i, j)$ 向上取整。例如，$\lceil 5 \rceil = 5$，$\lceil 5.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