Magic Square Generator

Given an integer ( n ), generate an ( n \times n ) magic square if possible. A magic square is a square arrangement of the numbers from 1 to ( n^2 ) in which every row, every column, and both main diagonals all add up to the same constant. The constant can be expressed as ( \frac{n(n^2+1)}{2} ). For some values of ( n ), it is impossible to construct a magic square. In this problem, if ( n ) does not meet the construction criteria, you should output exactly the string None.

Construction Criteria:

• \( 1 \le n \le 15 \)
• Either \( n \) is odd, or \( n \) is doubly even (i.e. \( n \equiv 0 \; (\bmod\; 4) \)). Additionally, \( n=4 \) is valid.

The magic square should be generated using the standard Siamese method for odd ( n ) and corresponding methods for doubly even orders. If a valid magic square can be generated, output its rows one per line with the numbers in each row separated by spaces. Otherwise, output None.

inputFormat

Input is read from standard input and consists of a single integer ( n ), representing the order of the magic square.

outputFormat

If a magic square of order ( n ) exists under the given constraints, output ( n ) lines where each line contains ( n ) space-separated integers representing a row of the magic square. If no valid magic square exists, output the string None.## sample

3

8 1 6
3 5 7
4 9 2