Constructing a Magic Square

Problem Description

In an $N \times N$ square grid, fill each cell with a distinct positive integer from $1$ to $N \times N$ so that the sums of the numbers in every row, every column, and both main diagonals are equal; such a square is called a "magic square" (the sample shows a $3 \times 3$ magic square). In ancient China it was called "Hetu", "Luoshu", or the "vertical-horizontal diagram".

A magic square looks magical, but when $N$ is odd there is a convenient construction:

1. Initially the square is empty. First, put $1$ in the exact centre of the top row.
2. From the last filled position, move up one cell; if already in the top row, wrap to the bottom row of the same column. Then move right one cell; if already in the rightmost column, wrap to the first column of the same row. If the new position is empty, fill it with the next number after the last filled one.
3. If step 2 fails (the target cell is already filled), instead move down one cell from the last filled position; if already in the bottom row, wrap to the top row of the same column. This position is guaranteed to be empty. Fill it with the next number after the last filled one.
4. Repeat steps 2 and 3 until all cells are filled, and the magic square is complete!

Write a program to construct an $N \times N$ magic square following the rules above.

Input Format

The input is a positive odd integer $N$, with $3 \le N \le 21$ guaranteed.

Output Format

Output $N$ lines, each containing $N$ space-separated positive integers: the $N \times N$ magic square.

Sample Input

3

Sample Output

8 1 6
3 5 7
4 9 2

Sample Explanation

For $N = 3$, following the odd-order magic square construction:

• Put $1$ in the centre of the top row, i.e. row 1, column 2.
• From $1$, move up and right: up goes to row 3 (wrapping past the top row to the bottom), right goes to column 3; position $(3,3)$ is empty, fill $2$.
• From $2$, move up and right: up to row 2, right to column 1 (wrapping past the rightmost column to the first); position $(2,1)$ is empty, fill $3$.
• From $3$, move up and right: up to row 1, right to column 2, but $(1,2)$ already holds $1$, so step 2 fails. Instead move down from $3$: down to row 3, column 1; position $(3,1)$ is empty, fill $4$.
• Continue applying the rule to fill $5$ through $9$, yielding the matrix above.

In this magic square, every row, every column, and both diagonals sum to $15$.

Constraints

$N$ is a positive odd integer with $3 \le N \le 21$.