Las Vegas 是一款易于上手的掷骰子桌游。玩家掷出骰子并将其投入到不同的赌场中，在每个赌场中投入骰子数量最多的玩家将赢得该赌场的奖金，但前提是不能出现平局！该游戏完美结合了运气与策略，并曾获得 2012 年德国年度游戏奖（Spiel des Jahres）提名。

照片由 @denislargeron 在 BoardGameGeek 上提供

考虑一个包含 $n$ 个赌场和 $(m + 1)$ 名玩家的游戏。你是第 $(m + 1)$ 名玩家，其他所有玩家都已经将骰子投入（或决定不投入）到各个赌场中。已知在第 $i$ 个赌场中，第 $j$ 名玩家投入了 $a_{i,j}$ 个骰子。

你的任务是决定对于每个 $1 \le i \le n$，你在第 $i$ 个赌场中投入的骰子数量 $b_i$。在你投入骰子后，我们将根据以下规则分别确定每个赌场的获胜者：

1. 首先，如果两个或更多的玩家在同一个赌场中投入了相同数量的骰子，那么他们在这个赌场中的所有骰子都将被移除。
2. 在此之后，在同一个赌场中投入骰子数量最多的玩家被确定为获胜者。如果该赌场中没有骰子，则没有获胜者。

例如：

• 考虑一个有 7 名玩家的赌场，他们分别投入了 1, 2, 3, 3, 4, 4, 4 个骰子。首先，由于有两名或更多玩家投入了 3 个或 4 个骰子，这些骰子全部被移除，剩余的骰子数量分别为 1, 2, 0, 0, 0, 0, 0。该赌场的获胜者是投入了 2 个骰子的玩家。
• 考虑一个有 4 名玩家的赌场，他们分别投入了 2, 3, 2, 3 个骰子。首先，由于有两名或更多玩家投入了 2 个或 3 个骰子，这些骰子全部被移除，剩余的骰子数量分别为 0, 0, 0, 0。由于该赌场中没有骰子，因此没有获胜者。

你的目标是在所有玩家中赢得数量最多的赌场。更准确地说，设 $w_i$ 为玩家 $i$ 获胜的赌场数量，必须满足 $w_{m+1} \ge w_i$，对于所有 $1 \le i \le m$ 均成立。在达成目标的前提下，最小化你在所有赌场中投入的骰子总数，即最小化 $\sum_{i=1}^{n} b_i$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 50$)，分别表示赌场的数量和玩家的数量（不包括你）。

接下来的 $n$ 行，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 10^8$)，其中 $a_{i,j}$ 表示第 $j$ 名玩家在第 $i$ 个赌场中投入的骰子数量。

保证满足 $n > 20$ 或 $m > 20$ 的测试数据不超过 3 组。

输出格式

对于每组测试数据，输出一行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$)，并用空格分隔，其中 $b_i$ 是你在第 $i$ 个赌场中投入的骰子数量。可以证明在上述 $b_i$ 的约束下，最优解总是存在的。如果存在多个最优解，你可以输出其中任意一个。

样例

样例输入 1

3
4 3
3 3 2
2 7 5
3 5 2
1 6 4
3 4
100 100 100 1
0 0 0 1
100 100 100 1
1 4
20 0 20 0

样例输出 1

4 0 6 0
1 0 2
0

说明

对于第一组样例，你是第 1 个和第 3 个赌场的获胜者，而玩家 2 是第 2 个和第 4 个赌场的获胜者。

对于第二组样例，你是第 3 个赌场的获胜者，而玩家 4 是第 2 个赌场的获胜者。第 1 个赌场没有获胜者。