That means choosing two points PP and QQ, where PP is on the ii-th sphere's surface or inside it, QQ is on the jj-th sphere's surface or inside it, and minimize the Euclidean distance bewteen PP and QQ.
There are n(n−1)2n(n−1)2 pairs of i,j(1≤i<j≤n)i,j(1≤i<j≤n), please find the kk-th smallest values among these d(i,j)d(i,j).
Input
The first line of the input contains an integer T(1≤T≤3)T(1≤T≤3), denoting the number of test cases.
In each test case, there are two integers n,k(2≤n≤100000,1≤k≤min(300,n(n−1)2))n,k(2≤n≤100000,1≤k≤min(300,n(n−1)2))in the first line, denoting the number of spheres and the parameter kk.
For the next nn lines, each line contains four integers xi,yi,zi,ri(0≤xi,yi,zi≤106,1≤ri≤106)xi,yi,zi,ri(0≤xi,yi,zi≤106,1≤ri≤106), denoting each sphere.
Output
For each test case, print kk lines, each line contains an integer, denoting the kk-th smallest values among these d(i,j)d(i,j). You should print them in non-decreasing order. To avoid precision error, print ⌈d(i,j)⌉⌈d(i,j)⌉ instead. For example, ⌈5⌉=5⌈5⌉=5, and ⌈5.1⌉=6⌈5.1⌉=6.