I. Xor Magic Square
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A good matrix of size $$$N$$$ is an $$$N \times N$$$ matrix of positive integers such that the total XOR of each row, each column, and both diagonals is $$$0$$$.

More precisely, an $$$N \times N$$$ matrix $$$A$$$ is called a good matrix of size $$$N$$$ if it satisfies all of the following conditions. Here, $$$x \oplus y$$$ denotes the bitwise XOR of $$$x$$$ and $$$y$$$, and $$$\displaystyle \bigoplus_{i=1}^{N} a_i = a_1 \oplus \ldots \oplus a_N$$$.

  • $$$A_{i, j}\ (1 \le i, j \le N)$$$ is a positive integer
  • For each $$$i = 1, 2, \ldots, N$$$, $$$\displaystyle \bigoplus_{j=1}^{N} A_{i,j}= 0$$$
  • For each $$$j = 1, 2, \ldots, N$$$, $$$\displaystyle \bigoplus_{i=1}^{N} A_{i,j}= 0$$$
  • $$$\displaystyle \bigoplus_{i=1}^{N} A_{i,i}= 0$$$
  • $$$\displaystyle \bigoplus_{i=1}^{N} A_{i,N-i+1}= 0$$$

A positive integer $$$N$$$ is given.

Among all good matrices of size $$$N$$$, output one whose total sum of all elements, $$$\displaystyle \sum_{1 \le i, j \le N} A_{i, j}$$$, is minimum.

If no good matrix of size $$$N$$$ exists, report that.

Input

The input consists of a single integer $$$N$$$. ($$$1 \le N \le 2 \times 10^3$$$)

Output

If no good matrix of size $$$N$$$ exists, print $$$-1$$$ on a single line.

If it exists, print the minimum possible total sum of all elements on the first line.

Then print the matrix $$$A$$$ in the following $$$N$$$ lines, with elements separated by spaces. That is, the $$$(i+1)$$$-th line should contain the elements of the $$$i$$$-th row of matrix $$$A$$$, separated by spaces.

If there are multiple solutions, any of them may be printed.

Examples
Input
2
Output
4
1 1
1 1
Input
1
Output
-1
Note

For the first example, the total XOR of each row, each column, and both diagonals is $$$0$$$, so it satisfies the conditions for a good matrix. Also, among all good matrices of size $$$2$$$, the total sum of all elements cannot be made smaller than $$$4$$$, so the minimum value is $$$4$$$.

For the second example, there is no good matrix of size $$$1$$$, so print $$$-1$$$.

The bitwise XOR $$$x \oplus y$$$ of non-negative integers $$$x,y$$$ is defined as follows.

  • In the binary representation of $$$x \oplus y$$$, the digit at the $$$2^k \ (k \geq 0)$$$ place is $$$1$$$ if and only if exactly one of the digits at the $$$2^k$$$ place in the binary representations of $$$x$$$ and $$$y$$$ is $$$1$$$; otherwise, it is $$$0$$$.

For example, $$$3 \oplus 5 = 6$$$ (in binary, $$$011 \oplus 101 = 110$$$).