숫자 배치하기

시간 제한2초메모리 제한1024 MB

요약

짝수 N에 대해 1부터 N^2/2까지의 각 수가 두 번씩 나타나고, 두 위치가 인접하지 않으며, 두 수를 포함하는 가장 작은 부분 행렬의 합이 그 수의 배수가 되도록 N×N 행렬을 출력한다.

문제

쿠는 아래의 조건을 만족하는 $N\times N$ 행렬을 찾고 싶어졌다. 이때 $N$ 은 짝수이다.

$1 \le p \le \frac{N^2}{2}$ 인 모든 양의 정수 $p$ 에 대해 아래의 조건을 만족한다.
- 행렬에 $p$ 가 정확히 $2$ 번 등장한다.
- $p$ 의 위치를 각각 $(r\_1, c\_1) , (r\_2, c\_2)$ 라 하자. 이때 $|r\_1 - r\_2| + |c\_1 - c\_2| > 1$ 이고, $(r\_1, c\_1) , (r\_2, c\_2)$ 를 포함하는 가장 작은 부분 행렬에 속한 값들의 합은 $p$ 의 배수이다.

쿠를 위해 조건을 만족하는 행렬을 아무거나 하나 출력해 보자. 조건을 만족하는 행렬이 하나 이상 존재함이 보장된다.

짝수인 양의 정수 $N$ 이 주어진다. $(2 \le N \le 1\\,000)$

$N$ 개의 줄에 걸쳐, 조건을 만족하는 행렬의 각 행에 속하는 $N$ 개의 값을 공백으로 구분하여 출력한다.