Description

Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?      

Input

The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.      

Output

For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.      

Sample Input

12 31 2 32 2 3

Sample Output

3 3 4

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int a[105][2005],b[2005];priority_queue
           
            p;int main() {    int T;    scanf("%d",&T);    while(T--){        int n ,m;        scanf("%d%d",&m,&n);           //m个序列，每个含n个数字        for(int i=0;i
            
             =0;t--){ if(j==0)p.push(a[i][0]+b[t]); //将第i个序列的第一项与加之i-1序列的前n小项相加 else{ if(p.top()>b[t]+a[i][j]){ p.pop(); p.push(a[i][j]+b[t]); } else break; } } } } for(int i=0;i
             
              =0;i--){ if(i==0)printf("%d\n",b[i]); else printf("%d ",b[i]); } } //system("pause"); return 0;}