젖소 간식

소들이 이번 달에도 우유 생산 기록을 새로 세워, 각자 특별한 간식을 받을 자격을 얻었습니다. 소들은 $W \times H$ 크기의 직사각형 대형($1 \le W \le 25$, $1 \le H \le 25$)을 빈틈없이 채운 채 간식을 기다리고 있습니다.

각 소는 전체 우유 생산 성과를 나타내는 서로 다른 능력치 $F_{rc}$($1 \le F_{rc} \le 1{,}000{,}000$)를 가지고 있습니다. 농부 존은 생산량이 높은 소부터 간식을 주려고 합니다. 그는 한 줄씩 간식을 나눠 주는데, 1행의 첫 번째 열부터 마지막 열까지 차례로 준 뒤 2행으로 넘어가는 식으로 진행합니다. 따라서 간식을 주는 순서는 다음과 같습니다.

1    2    3   ...  W
W+1  W+2  W+3 ...  2W
...

농부 존은 생산량이 좋은 소일수록 먼저 간식을 받도록 소들에게 자리를 다시 배치하라고 부탁합니다. 하지만 소들은 자유롭게 정렬하지 못하고, 대형에서 두 행 전체를 맞바꾸거나 두 열 전체를 맞바꾸는 것만 할 수 있습니다. 이 두 가지 이동만으로 소들은 최선을 다해, 능력치가 가장 높은 소를 왼쪽 위 모서리(1행 1열)에 두고 그다음으로 높은 소를 가능한 한 앞 순서에 두는 식으로 다음 그리디 규칙을 따릅니다.

• 능력치가 가장 높은 소를 찾습니다. 행과 열을 맞바꿔 그 소를 1행 1열로 옮긴 뒤, 다시는 움직이지 않도록 고정합니다.
• 더 이상 개선할 소가 없을 때까지 다음을 반복합니다. 아직 고정되지 않은 소 중 능력치가 가장 높은 소를 골라, 이미 고정된 더 높은 소를 움직이지 않으면서 행이나 열을 맞바꿔 아직 도달할 수 있는 가장 앞 순서의 자리로 옮깁니다(예: 1행 2열에 갈 수 있으면 그곳, 그렇지 못하면 2행 1열, 이런 식으로). 그 자리에 도달하면 그 소를 고정하며, 이후 그 소의 행과 열은 더 이상 맞바꿀 수 없습니다.

어떤 소는 현재 자신의 행과 열이 모두 아직 고정되지 않았을 때에만 옮길 수 있습니다. 행만 고정된 경우에는 그 행에 머문 채 열만 바꿀 수 있고, 열만 고정된 경우에는 행만 바꿀 수 있으며, 둘 다 고정된 경우에는 전혀 움직일 수 없습니다.

예시 (3행 4열):

5  7  4  1
9 99  2  6
8  3 10 11

능력치 99인 소가 가장 뛰어나므로 왼쪽 위 모서리에 와야 합니다. 1행과 2행을 맞바꾼 뒤 1열과 2열을 맞바꾸면 다음과 같습니다.

99  9  2  6
 7  5  4  1
 3  8 10 11

능력치 11인 소는 99 바로 다음으로 간식을 받아야 합니다. 이 소는 가장 마지막 순서인 (3, 4) 자리에 있어서 이미 1행이나 1열에 도달하기에는 늦었고, 갈 수 있는 가장 앞 자리는 (2, 2)입니다. 2열과 4열을 맞바꾼 뒤 2행과 3행을 맞바꾸면 다음과 같습니다.

2열과 4열 교환          2행과 3행 교환
99   6  2  9            99   6  2  9
 7   1  4  5      ->     3  11 10  8
 3  11 10  8            7   1  4  5

능력치 10인 소는 11 바로 다음 순서인 자기 자리에 그대로 고정됩니다. 9는 이미 간식을 받았습니다. 8은 10 바로 다음, 7은 8 바로 다음입니다. 6은 이미 받았습니다. 능력치 5인 소는 3행 2열로 가고 싶지만 1행과 2행, 그리고 모든 열이 이미 고정되어 있어 1, 4와 마찬가지로 움직일 수 없습니다. 따라서 위 대형이 소들이 만들 수 있는 최선의 배치입니다.

처음 대형이 주어지면, 이 그리디 절차로 소들이 도달하는 최종 대형을 출력하세요.

• 첫째 줄: 공백으로 구분된 두 정수 $W$와 $H$.
• 둘째 줄부터 $H+1$번째 줄까지: $i+1$번째 줄에는 $i$행의 값 $F_{ic}$($c = 1 \dots W$)가 공백으로 구분되어 $W$개 주어집니다.

• 첫째 줄부터 $H$번째 줄까지: $i$번째 줄에는 소들의 최종 대형에서 $i$행에 해당하는 정수 $W$개를 공백으로 구분해 출력합니다.