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$ 獲勝的賭場數量，必須滿足對於所有 $1 \le i \le m$，都有 $w_{m+1} \ge w_i$。在達成目標的前提下，最小化你在所有賭場放置的骰子總數。也就是說，最小化 $\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 沒有贏家。