Zauberquadrat und Sudoku

지수는 독일에 유학을 가있는 동안 열렬한 수학 퍼즐 마니아 조슈아 뮐러와 친해졌다. 조슈아는 수학 퍼즐 중에서 마방진(Zauberquadrat)과 스도쿠(Sudoku)를 좋아하는데, 조슈아의 말에 의하면 ‘사람들이 스도쿠는 언제 풀어도 재미있다고 생각하지만, 마방진은 쉬운 풀이 방법이 잘 알려져 있어서 잘 풀지 않는다.’라고 한다.

마방진의 정의는 다음과 같다.

• 마방진의 게임판은 $N \times N$ 크기의 격자 모양이다.
• 게임판의 각 칸에는 $1$ 이상 $N^2$ 이하의 정수를 정확히 한 번씩 써야 한다.
• 게임판의 $N$개의 가로줄과 $N$개의 세로줄, 2개의 대각선에 대하여 각 영역에 있는 수들의 합이 항상 같아야 한다.

스도쿠의 정의는 다음과 같다.

• 스도쿠의 게임판은 $N^2 \times N^2$ 크기의 격자 모양이며, 게임판은 $N \times N$ 크기의 작은 게임판 $N^2$개로 쪼개져있다.
• 게임판의 각 칸에는 $1$ 이상 $N^2$ 이하의 정수를 쓸 수 있다.
• 게임판의 $N^2$개의 가로줄과 $N^2$개의 세로줄, $N^2$개의 작은 게임판에 대하여 각 영역에는 $1$ 이상 $N^2$ 이하의 정수들이 정확히 한 번 나타나야 한다.

조슈아는 사람들에게 마방진의 위대함을 알리기 위해서 마방진을 스도쿠와 접목시키려고 한다. 조슈아는 $N^2 \times N^2$ 스도쿠에서 $N^2$개의 작은 게임판들이 모두 마방진이 되게 퍼즐을 만들 생각을 해보았다. 조슈아는 $N = 3$이면 이런 퍼즐을 만드는 것이 불가능하다는 것을 쉽게 알 수 있었다. 잠시 후 조슈아는 자신의 조건을 만족시키는 $16 \times 16 (N = 4)$ 퍼즐을 쉽게 만들었다.

조슈아는 지수에게 자신의 조건을 만족하는 $16 \times 16$ 퍼즐을 만들어보라고 한다. 지수는 현재 연구실에서 인턴을 하느라 바쁘므로, 지수 대신 당신이 $16 \times 16$ 퍼즐을 만들어보자.

입력은 없다.

16개의 줄에 걸쳐, 만들어진 퍼즐을 출력한다. 답이 여러 개 있으면 아무거나 출력한다.