Description

We introduce a new chess piece on the board, called the “camel”. Its jumping rules are as follows: you may move it to a position in the horizontal or vertical direction such that there are $2$ squares between the new position and the old one; or move it in one of the four diagonal directions such that there is exactly one square between the new position and the old one. As shown in the figure, the center of the board is the piece’s position, and the $8$ positions marked with “$\times$” are the positions it can move to. Clearly, the piece cannot jump outside the board.

The whole board has $N$ rows and $N$ columns, and it is guaranteed that $5 \mid N$.

At the beginning, the piece is in the upper-left corner of the board. After a sequence of moves, every square on the board is visited exactly once, and the final position and the starting position are mutually reachable in exactly one camel move. This is called a “camel cycle”.

You need to write a program to find a “camel cycle” for the given board, or determine whether a “camel cycle” exists.

Input Format

The input contains only one line: a positive integer $N$.

Output Format

First, if it does not exist, output NO.

Otherwise, output an $N \times N$ square matrix.

The matrix contains $N^2$ distinct positive integers in the range $[1, N^2]$, representing the visiting order of each square. The first number is $1$.

For example, if the number in row $i$ and column $j$ is $k$, it means that this square is the $k$-th square visited. See the sample for details.

10

1 52 29 8 51 28 9 50 37 16
85 95 59 86 94 66 87 93 65 88
40 19 100 39 18 76 38 17 77 49
2 53 30 7 58 27 10 89 36 15
84 96 60 75 99 67 72 92 64 71
41 20 82 44 23 90 45 24 78 48
3 54 31 6 57 26 11 68 35 14
83 97 61 74 98 62 73 91 63 70
42 21 81 43 22 80 46 25 79 47
4 55 32 5 56 33 12 69 34 13

Hint

Special Judge Scoring Rules

If there are multiple feasible solutions, outputting any one of them is enough to get the score for that test point.

If your output is incomplete or found to be incorrect, you may get a UKE.

If you output NO where you should not output NO, you will get WA, along with the message wrong output format Expected integer, but "NO" found.

Explanation of the Sample

The piece moves as: $(1,1)$ (meaning row $1$, column $1$) $\rightarrow (4,1) \rightarrow (7,1) \rightarrow \text{etc.}$

Finally, the piece stops at $(3,3)$, and it can reach the starting position in exactly one move.

Illustration:

Constraints

For all testdata, it is guaranteed that $1 \le N \le 10^3$, and $n$ is a multiple of $5$.

There are $17$ test points in total.

• For one test point, $N = 5$, and its score ratio is $20\%$.
• For the other $16$ test points, there are no additional constraints, and each has a score ratio of $5\%$.

Notes

The original problem is from: eJOI2017 Problem D Camel

Translation provided by: @_Wallace_

Translated by ChatGPT 5