34725번 - 직사각형 채우기 스페셜 저지

크기가 $N \times M$인 격자(두 값 모두 짝수)가 주어진다. 격자의 각 칸에 정수 하나를 채울 것이다.

사용할 수 있는 정수는 $1, 2, \dots, K$이며 $K = N*M/4$ 이다. 각 정수 $k$ $(1 \le k \le K)$는 정확히 4번 등장해야 하며, 그 4칸은 축에 평행한 하나의 직사각형의 네 꼭짓점을 이루어야 한다. (즉, 서로 다른 두 개의 행과 서로 다른 두 개의 열을 선택했을 때 생기는 네 모서리 칸을 써야 한다.)

각 정수 $k$가 만든 직사각형의 넓이를 $area(k)$라고 하자. 직사각형의 두 행 인덱스를 $r_1 < r_2$, 두 열 인덱스를 $c_1 < c_2$라고 하면 $area(k) = (r_2 - r_1) * (c_2 - c_1)$

전체 점수는 $area(1) + area(2) + \dots + area(K)$ 이다.

점수를 최대로 만드는 유효한 배치를 하나 출력하라. 여러 정답이 가능하면 아무거나 출력해도 된다.

항상 가능한 입력만 주어진다.

첫째 줄에 두 정수 $N, M$이 주어진다.

유효하고 점수가 최대가 되는 배치를 한 가지 출력한다.

• $N$줄에 걸쳐 각 줄마다 $M$개의 정수를 공백으로 구분하여 출력한다.
• 각 정수는 $1$ 이상 $K$ 이하이며, $K = N*M/4$ 이다.
• 각 $k$는 정확히 4개 칸에 배치되어야 하며, 그 4칸은 서로 다른 두 행과 서로 다른 두 열의 조합으로 이루는 직사각형의 네 꼭짓점이어야 한다.
• 여러 최적 해가 존재하면 그중 아무거나 출력해도 된다.

• $2 \le N, M \le 1000$
• $N$과 $M$은 짝수