수상식

학생들은 힘든 기말 고사 기간이 지나고, 각자 특별한 보상을 받게 됩니다. 학생들은 W x H (1 <= W <= 25; 1 <= H <= 25) 직사각형 배열을 채우며 앉아있습니다.

각 학생은 고유한 F_rc (1 <= F_rc <= 1,000,000) 값의 성적을 가지고 있습니다. 이것은 해당 학생의 전반적인 시험 성적를 나타냅니다. 교장선생님은 가장 높은 성적을 받은 학생들에게 먼저 보상을 주는 것이 공정하다고 생각합니다. 그는 직사각형 배열에서 행 단위로 순회합니다. 즉 1행에서 시작하여 1행에서 모든 보상을 나눠 준 후에야 2행으로 넘어가는 방식으로 수상을 진행할 계획입니다.

교장선생님은 성적이 높은 학생들이 먼저 보상을 받을 수 있도록 학생들에게 자리를 재배치하라고 요청했지만 학생들은 자리를 재배치하는데 능숙하지 않았습니다. 학생들은 배열의 행 한개 교환하거나 열 한 개를 교환하는 것 정도만 가능합니다. 교장 선생님은 학생들이 할 수 있는 최선의 방법으로 처음에 가장 우수한 학생를 왼쪽 위 모서리(행 1, 열 1)로 이동시키고, 그 다음 우수한 학생을 행 1, 열 2로 이동시키라고 요청했습니다. 물론, 학생들은 완벽하게 정렬하지는 못하지만, 이 기준을 지키기 위해 노력했습니다:

교장선생님의 보상 수상 순서를 결정하십시오:

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

평가가 가장 높은 학생을 찾고, 그가 행 1, 열 1에 위치할 때까지 행과 열을 변경하십시오; 그 후에는 그 학생을 움직이지 마십시오

• 그 다음 이 규칙을 가능한 한 많은 학생들이 위치할 때까지 실행하십시오:
• 성적이 다음으로 높은 학생을 찾아 봅니다. 행과 열을 교환하여 그를 가능한 한 가장 알맞은 위치(가능하면 행 1, 열 2 또는 행 1에서 자리를 찾지 못한 경우 행 2, 열 1)로 이동시킵니다.

예를 들어, 3 x 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점을 받은 학생은 가장 평가가 높은 암소 다음으로 보상을 받아야 합니다. 그 학생은 현재 슬롯 (3,4), 즉 제일 마지막으로 받게 될 슬롯에 있습니다. 이 시점에서는 그 학생을 첫 번째 행이나 첫 번째 열로 바꾸기에는 너무 늦었습니다. 따라서 열 2와 4를 교환한 다음 행 2와 3를 교환하여 학생을 (2,2)로 이동시켜야 합니다:

       Swap cols 2 and 4     Swap rows 2 and 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,5는 움직이지 않고, 위의 두 번째 다이어그램이 '학생들이 할 수 있는 최선'입니다.

다른 직사각형 배열의 학생들에 대해 이 알고리즘을 구현하십시오.

• 첫 번째 줄 : 두 개의 공백으로 구분된 정수: W와 H
• 두 번째 줄부터 H+1 번째 줄 : i+1번째 줄에는 W개의 공백으로 구분된 정수 F_ic가 포함됩니다. 여기서 c는 1에서 W까지 범위를 가집니다.

• 첫 번째 줄부터 H 번째 줄 : i 번째 줄에는 학생들의 최종 배치에서 i번째 행을 나타내는 W개의 공백으로 구분된 정수가 포함됩니다.