35054번 - Hearty Sudoku 스페셜 저지

문제

양의 정수 $N\ge 2$에 대해, $N$차 스도쿠를 다음과 같이 정의한다.

• $N^2\times N^2$ 크기의 사각 격자를 $N\times N$ 크기의 겹치지 않는 정사각형 영역(박스) $N^2$개로 나눈다.
• 각 칸에 1ドル$ 이상 $N^2$ 이하의 정수를 하나씩 채우는데, 각각의 가로줄, 각각의 세로줄, 각각의 박스에 1ドル$부터 $N^2$까지의 정수가 정확히 한 번씩 등장해야 한다.

각각의 박스에 대해, 맨 윗줄의 맨 왼쪽에서 오른쪽으로 순서대로 1ドル$번부터 $N$번, 그다음 줄의 왼쪽부터 오른쪽으로 순서대로 $N+1$번부터 2ドルN$번, $\cdots$과 같이 번호를 붙인다. 각 가로줄과 세로줄에도 맨 위의 가로줄부터 순서대로, 맨 왼쪽의 세로줄부터 순서대로 번호를 붙인다.

그리고 완성된 스도쿠의 각 칸에 대해, 그 칸이 쓰인 수가 그 칸의 가로줄 번호, 세로줄 번호, 박스 번호 중 적어도 하나와 같다면 그 칸에 하트를 그린다.

이때 하트의 개수를 최대화하는 스도쿠를 아무거나 하나 출력하시오.

입력

첫째 줄에 $N$이 주어진다. (2ドル\le N\le 20$)

출력

문제의 조건을 충족하는 스도쿠를 출력한다. $N^2$개의 줄에 걸쳐 $i$번째 줄에는 스도쿠의 $i$번째 가로줄에 쓰여 있는 $N^2$개의 수를 순서대로 공백으로 구분하여 출력한다.

제한

노트