Las Vegas to łatwa do nauczenia gra planszowa polegająca na rzucaniu kośćmi. Gracze rzucają kośćmi i umieszczają je w jednym z kasyn, a gracz z największą liczbą kości w danym kasynie wygrywa jego pieniądze, ale tylko wtedy, gdy nie ma remisu! Gra doskonale łączy szczęście ze strategią i była nominowana do nagrody Spiel des Jahres w 2012 roku.

Zdjęcie autorstwa @denislargeron na BoardGameGeek

Rozważ grę z $n$ kasynami i $(m + 1)$ graczami. Jesteś $(m + 1)$-szym graczem, a wszyscy pozostali gracze już umieścili (lub zdecydowali się nie umieszczać) swoje kości w kasynach. Wiadomo, że w $i$-tym kasynie $j$-ty gracz umieścił $a_{i,j}$ kości.

Twoim zadaniem jest zdecydować o liczbie kości $b_i$, które chcesz umieścić w $i$-tym kasynie dla każdego $1 \le i \le n$. Po umieszczeniu Twoich kości, wyłonimy zwycięzcę każdego kasyna z osobna zgodnie z następującą zasadą:

1. Najpierw, jeśli dwóch lub więcej graczy umieściło taką samą liczbę kości w tym kasynie, wszystkie ich kości w tym kasynie zostają usunięte.
2. Następnie gracz z największą liczbą kości w tym kasynie zostaje uznany za zwycięzcę. Jeśli w kasynie nie ma żadnych kości, nie ma zwycięzcy.

Na przykład:

• Rozważ kasyno, w którym 7 graczy umieściło odpowiednio 1, 2, 3, 3, 4, 4, 4 kości. Najpierw, ponieważ jest dwóch lub więcej graczy z 3 lub 4 kośćmi, wszystkie ich kości zostają usunięte, a pozostała liczba kości wynosi odpowiednio 1, 2, 0, 0, 0, 0, 0. Zwycięzcą tego kasyna jest gracz z 2 kośćmi.
• Rozważ kasyno, w którym 4 graczy umieściło odpowiednio 2, 3, 2, 3 kości. Najpierw, ponieważ jest dwóch lub więcej graczy z 2 lub 3 kośćmi, wszystkie ich kości zostają usunięte, a pozostała liczba kości wynosi odpowiednio 0, 0, 0, 0. Ponieważ w tym kasynie nie ma żadnych kości, nie ma zwycięzcy.

Twoim celem jest wygranie w największej liczbie kasyn spośród wszystkich graczy. Mówiąc dokładniej, niech $w_i$ będzie liczbą kasyn, w których zwycięzcą jest gracz $i$; musi zachodzić $w_{m+1} \ge w_i$ dla wszystkich $1 \le i \le m$. Zminimalizuj całkowitą liczbę kości, które umieścisz we wszystkich kasynach, osiągając swój cel. To znaczy, zminimalizuj $\sum_{i=1}^{n} b_i$.

Wejście

Istnieje wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera dwie liczby całkowite $n$ i $m$ ($1 \le n, m \le 50$), określające liczbę kasyn oraz liczbę graczy (poza Tobą).

W kolejnych $n$ liniach, $i$-ta linia zawiera $m$ liczb całkowitych $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 10^8$), gdzie $a_{i,j}$ to liczba kości w kasynie $i$ umieszczona przez gracza $j$.

Gwarantuje się, że istnieje co najwyżej 3 zestawy danych spełniające $n > 20$ lub $m > 20$.

Wyjście

Dla każdego zestawu danych wypisz jedną linię zawierającą $n$ liczb całkowitych $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$) oddzielonych spacją, gdzie $b_i$ to liczba kości, które umieszczasz w kasynie $i$. Można udowodnić, że przy takich ograniczeniach na $b_i$ zawsze istnieje optymalne rozwiązanie. Jeśli istnieje wiele optymalnych rozwiązań, możesz wypisać dowolne z nich.

Przykład

Wejście 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

Wyjście 1

4 0 6 0
1 0 2
0

Uwagi

Dla pierwszego przykładowego zestawu danych, jesteś zwycięzcą kasyna 1 i 3, podczas gdy gracz 2 jest zwycięzcą kasyna 2 i 4.

Dla drugiego przykładowego zestawu danych, jesteś zwycięzcą kasyna 3, podczas gdy gracz 4 jest zwycięzcą kasyna 2. W kasynie 1 nie ma zwycięzcy.