Chạy bộ buổi sáng

Có một đường chạy với $n+1$ trạm kiểm soát được đánh số $0,1,\dots ,n$. Mỗi vận động viên xuất phát ở trạm $0$ và về đích ở trạm $n$, đi lần lượt qua tất cả các trạm theo thứ tự (từ trạm $i-1$ sang trạm $i$).

Giữa hai trạm liền kề $i-1$ và $i$ có đúng $m$ con đường khác nhau; con đường thứ $j$ có độ dài $b_{i,j}$. Có $m$ vận động viên. Mỗi cặp trạm liền kề, mỗi con đường phải được đúng một vận động viên chạy qua. Nói cách khác, ở mỗi chặng $i$, ta phân phối $m$ con đường cho $m$ vận động viên (mỗi người một con đường).

Nếu một vận động viên chạy các con đường có độ dài $l_1,l_2,\dots ,l_n$ (ở các chặng $1,2,\dots ,n$) thì độ mệt của người đó bằng ${min}_{i=1}^n{l}_i$, tức con đường ngắn nhất mà người đó đã chạy.

Hãy sắp xếp việc phân phối các con đường sao cho tổng độ mệt của $m$ vận động viên là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa số lượng bộ test $t$.
• Với mỗi bộ test:
  • Dòng đầu chứa hai số nguyên $n$ và $m$.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa $m$ số nguyên $b_{i,1},b_{i,2},\dots ,b_{i,m}$.

Dữ liệu ra

Với mỗi bộ test, in ra $n$ dòng. Dòng thứ $i$ chứa $m$ số: độ dài các con đường mà vận động viên $1,2,\dots ,m$ chạy ở chặng $i$. Các số trên dòng thứ $i$ phải là một hoán vị của $b_{i,1},\dots ,b_{i,m}$.

Nếu có nhiều cách đạt tổng độ mệt nhỏ nhất, in ra một cách bất kỳ.

Ràng buộc

• $1\le t\le 10000$
• $1\le n,m\le 100$
• $1\le b_{i,j}\le {10}^9$
• Tổng của $n·m$ trên tất cả các bộ test không vượt quá ${10}^4$.

Ví dụ