题目描述

给定 $m$ 个序列，每个包含 $n$ 个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有 $m$ 个整数的序列。

很明显，我们一共可以得到 $n^m$ 个这种序列，然后我们可以计算每个序列中的数字之和，并得到 $n^m$ 个值。

现在请你求出这些序列和之中最小的 $n$ 个值。

输入格式

第一行输入一个整数 $T$，代表输入中包含测试用例的数量。

接下来输入 $T$ 组测试用例。

对于每组测试用例，第一行输入两个整数 $m$ 和 $n$。

接下来 $m$ 行输入 $m$ 个整数序列，数列中的整数均不超过 10000。

输出格式

对于每组测试用例，均以递增顺序输出最小的 $n$ 个序列和，数值之间用空格隔开。

每组输出占一行。

样例

输入样例：

1
2 3
1 2 3
2 2 3

输出样例：

3 3 4

样例解释

$m=2$ 个序列，每个序列有 $n=3$ 个数：

序列1: 1, 2, 3
序列2: 2, 2, 3

所有可能的组合（序列1取一个，序列2取一个）：

• 1+2=3
• 1+2=3
• 1+3=4
• 2+2=4
• 2+2=4
• 2+3=5
• 3+2=5
• 3+2=5
• 3+3=6

最小的 $n=3$ 个值是 3, 3, 4。

数据范围

• $0 < m \leq 1000$
• $0 < n \leq 2000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB