在三维空间中有 $ 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(300, \frac{n(n-1)}{2}) )$ 的一行开始，分别表示球体的数量和参数 $ 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