A magic square is a N by N matrix consisting of numbers <1, 2, .., N*N> such that (1) Every entry is unique. (2) Every row, column and the two main diagonals have the same sum.
For example, this is a 3 by 3 magic square:
8 1 6
3 5 7
4 9 2
Each row, column and the two main diagonals sum up to 15.
When N is odd, there is a simple way to generate the magic square:
1. Start at the centre of the first row, and put the number 1.
2. Every subsequent number is placed above and to the right of the previous number (wrap around if the number goes off the board).
3. If this cannot be done, then place the next number below the current one.
An example will clear this up:
x 1 x x 1 x x 1 x x 1 x x 1 x x 1 6 x 1 6 8 1 6 8 1 6
x x x -> x x x -> 3 x x -> 3 x x -> 3 5 x -> 3 5 x -> 3 5 7 -> 3 5 7 -> 3 5 7
x x x x x 2 x x 2 4 x 2 4 x 2 4 x 2 4 x 2 4 x 2 4 9 2
Rule no: (1) (2) (2) (3) (2) (2) (3) (2) (2)
Your task: Given N, output the N by N magic square.
Input
The input file will contain a single integer
N (1 ≤
N ≤ 100). You may assume that
N is odd.
Output
Output the magic square with
N numbers per line for
N lines. You do not have to worry about aligning the numbers.
Sample Input 1
3
Sample Output 1
8 1 6
3 5 7
4 9 2
Sample Input 2
5
Sample Output 2
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9