Spiral 123
We shall name a square matrix as spiral123 if it has the following properties:
- its elements are from the {0, 1, 2, 3} set;
- each row and column contains each of the values 1, 2 and 3, exactly once and all the other values are 0;
- starting from the upper-left corner going right, moving in spiral, the non-zero values will appear in the following order 1, 2, 3, 1, 2, 3, ... , 1, 2, 3.
For example a 5x5 spiral123 matrix is the following:
For a given natural number n, you should generate a nxn spiral123 matrix.
Input
The input contains only one natural number n (5 <= n <= 200) on the first line.
Output
If there is solution, the output must contain n lines, each with n numbers separated with one space, representing the required matrix. There can be many solutions, any of them can be written.
If there is no solution, on the single line of the output, the -1 value will be written.
Constraints
Time limit: 1 second
Memory limit: 64 megabytes
Examples
input 5 | output 0 1 0 2 3 0 2 3 0 1 1 3 0 0 2 3 0 2 1 0 2 0 1 3 0 |
another correct solution would be:
0 1 2 3 0
2 3 0 0 1
0 0 3 1 2
1 0 0 2 3
3 2 1 0 0