B'Elsie is learning how to paint. She has a canvas of n cells numbered from 1 to n and can paint any (potentially empty) subset of cells. Elsie has a 2D array a which she will use to evaluate paintings. Let the maximal contiguous intervals of painted cells in a painting be [l_1,r_1],[l_2,r_2], ldots,[l_x,r_x] . The beauty of the painting is the sum of a_{l_i,r_i} over all 1 <= i <= x . In the image above, the maximal contiguous intervals of painted cells are [2,4],[6,6],[8,9] and the beauty of the painting is a_{2,4}+a_{6,6}+a_{8,9} . There are 2^n ways to paint the strip. Help Elsie find the k largest possible values of the beauty of a painting she can obtain, among all these ways. Note that these k values do not necessarily have to be distinct. It is guaranteed that there are at least k different ways to paint the canvas. The first line contains a single integer t ( 1 <= q t <= q 10^3 ) -- the number of test cases. The first line of each test case contains 2 integers n and k ( 1 <= q n <= q 10^3 , 1 <= q k <= q min(2^n, 5 cdot 10^3) ) -- the number of cells and the number of largest values of the beauty of a painting you must find. The next n lines of each test case describe a where the i -th of which contains n-i+1 integers a_{i,i},a_{i,i+1}, ldots,a_{i,n} ( -10^6 <= q a_{i,j} <= q 10^6 ). It is guaranteed the sum of n over all test cases does not exceed 10^3 and the sum of k over all test cases does not exceed 5 cdot 10^3 . For each test case, output k integers in one line: the i -th of them must represent the i -th largest value of the beauty of a painting Elsie can obtain. In the first test case, Elsie can either paint the only cell or not paint it. If she paints the only cell, the beauty of the painting is -5 . If she chooses not to paint it, the beauty of'...