Las Vegas は、習得が容易なダイスを振るボードゲームです。プレイヤーはダイスを振り、いずれかのカジノに配置します。カジノに最も多くのダイスを置いたプレイヤーがそのカジノの賞金を獲得しますが、同数のプレイヤーがいる場合は獲得できません。このゲームは運と戦略を完璧に組み合わせたもので、2012年にはドイツ年間ゲーム大賞（Spiel des Jahres）にノミネートされました。

Photo by @denislargeron on BoardGameGeek

$n$ 個のカジノと $(m + 1)$ 人のプレイヤーがいるゲームを考えます。あなたは $(m + 1)$ 番目のプレイヤーであり、他のすべてのプレイヤーはすでにカジノにダイスを配置済み（または配置しないことを決定済み）です。$i$ 番目のカジノにおいて、$j$ 番目のプレイヤーが $a_{i,j}$ 個のダイスを置いていることがわかっています。

あなたのタスクは、各 $1 \le i \le n$ について、$i$ 番目のカジノに置くダイスの数 $b_i$ を決定することです。あなたがダイスを置いた後、各カジノの勝者を以下のルールに従って個別に決定します。

1. まず、そのカジノに同じ数のダイスを置いているプレイヤーが2人以上いる場合、それらのプレイヤーのそのカジノにあるダイスはすべて取り除かれます。
2. その後、そのカジノに最も多くのダイスを置いているプレイヤーが勝者となります。カジノにダイスが残っていない場合、勝者はいません。

例：

• 7人のプレイヤーがそれぞれ 1, 2, 3, 3, 4, 4, 4 個のダイスを置いているカジノを考えます。まず、3個または4個のダイスを置いているプレイヤーが2人以上いるため、それらのダイスはすべて取り除かれ、残りのダイス数はそれぞれ 1, 2, 0, 0, 0, 0, 0 となります。このカジノの勝者は、2個のダイスを置いているプレイヤーです。
• 4人のプレイヤーがそれぞれ 2, 3, 2, 3 個のダイスを置いているカジノを考えます。まず、2個または3個のダイスを置いているプレイヤーが2人以上いるため、それらのダイスはすべて取り除かれ、残りのダイス数は 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}$ は $i$ 番目のカジノに $j$ 番目のプレイヤーが置いたダイスの数を表します。

$n > 20$ または $m > 20$ を満たすテストケースは最大で3つであることが保証されています。

出力

各テストケースについて、$n$ 個の整数 $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$) をスペース区切りで1行に出力してください。ここで $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の勝者です。

2番目のサンプルテストケースでは、あなたはカジノ3の勝者であり、プレイヤー4がカジノ2の勝者です。カジノ1には勝者がいません。