艺术联合会

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

艺术联合会顾名思义就是n个画家用n种颜色一起进行艺术创作(作画)。每一位画家仅使用一种颜色,并且规定n位画家使用的颜色是不同的,这里我们可以假设第一位画家使用的颜色编号为1,第2位画家使用的颜色编号为2以此类推。每一幅画上面都有n种颜色。我们假设把第j种颜色涂在第i幅画上需要消耗第j个画家的时间为 t[i][j]。
我们知道在任何情况下,规则都是至关重要的,因此画家们将根据以下规则进行作画:
1. 每一幅画都是由第一个画家先画,然后是第二个画家,然后是第三个画家……,也就是说,在第j个画家画完之后,一定是第(j + 1) 个画家进行作画 (如果有(j + 1)<= n)
2. 每一个画家在作画上按照这样的顺序进行作画:首先在第一幅画上作画,然后是第二幅画,依次类推直到第n幅画。
3. 不同的画家在不同的画幅上是可以同时工作的,比如说第二位画家在作第一幅画时,第一位画家可以作第二幅画。任何一个画家是不需要时间休息的。
4. 当第j个画家作完自己部分的画时,此幅画就立即可以被第(j + 1) 个画家使用。
 
假设第一位画家开始作画的时间是0,输出每一幅画被完成时的时间。

Input

第一行输入一个数T,表示有T组数据(1<=T<=100)。
每组数据第一行是两个整数:m 和 n(1 <= m <= 50000,1 <= n <= 5)m代表的是画幅的个数,n代表的是画家的个数。接下来每行有n个整数t[i][1],t[i][2]……t[i][n](1 <= t[i][j] <= 1000),t[i][j] 表示第j个画家把第j种颜色涂在第i幅画上需要的时间。

Output

每组数据输出一行含有m个数 r1,r2,……rm,这里ri表示第i幅画被完成时的时间。

Sample Input

2
5 1
1
2
3
4
5
4 2
2 5
3 1
5 3
10 1

Sample Output

1 3 6 10 15
7 8 13 21

Hint

 

Source