给定m个数字序列，每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列，显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和，一共会得到n^m个和，请找出最小的n个和。

输入格式

输入的第一行是一个整数T，表示测试用例的数量，接下来是T个测试用例的输入。 每个测试用例输入的第一行是两个正整数m（0 < m <= 100）和n(0 < n <= 2000)，然后有m行，每行有n个数，数字之间用空格分开，表示这m个序列。 序列中的数字不会大于10000。

输出格式

对每组测试用例，输出一行用空格隔开的数，表示最小的n个和。

输入样例

1
2 3
1 2 3
2 2 3

输出样例

3 3 4

限制

时间限制：3000，内存限制：65536