Una matriz buena de tamaño $N$ es una matriz de $N \times N$ de enteros positivos tal que el XOR total de cada fila, cada columna y ambas diagonales es 0.

Más precisamente, una matriz $A$ de $N \times N$ se denomina matriz buena de tamaño $N$ si satisface todas las siguientes condiciones. Aquí, $x \oplus y$ denota el XOR bit a bit de $x$ e $y$, y $\bigoplus_{i=1}^{N} a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \leq i, j \leq N$) es un entero positivo.
• Para cada $i = 1, 2, \dots, N$, $\bigoplus_{j=1}^{N} A_{i,j} = 0$.
• Para cada $j = 1, 2, \dots, N$, $\bigoplus_{i=1}^{N} A_{i,j} = 0$.
• $\bigoplus_{i=1}^{N} A_{i,i} = 0$.
• $\bigoplus_{i=1}^{N} A_{i,N-i+1} = 0$.

Se proporciona un entero positivo $N$. Entre todas las matrices buenas de tamaño $N$, imprima una cuya suma total de todos sus elementos, $\sum_{1 \leq i,j \leq N} A_{i,j}$, sea mínima. Si no existe ninguna matriz buena de tamaño $N$, infórmelo.

Entrada

La entrada consiste en un único entero $N$ ($1 \leq N \leq 2 \times 10^3$).

Salida

Si no existe ninguna matriz buena de tamaño $N$, imprima $-1$ en una sola línea. Si existe, imprima la suma total mínima posible de todos los elementos en la primera línea. Luego, imprima la matriz $A$ en las siguientes $N$ líneas, con los elementos separados por espacios. Es decir, la línea $(i+1)$-ésima debe contener los elementos de la fila $i$-ésima de la matriz $A$, separados por espacios. Si hay múltiples soluciones, se puede imprimir cualquiera de ellas.

Ejemplos

Entrada 1

2

Salida 1

4
1 1
1 1

Entrada 2

1

Salida 2

-1

Nota

Para el primer ejemplo, el XOR total de cada fila, cada columna y ambas diagonales es 0, por lo que satisface las condiciones de una matriz buena. Además, entre todas las matrices buenas de tamaño 2, la suma total de todos los elementos no puede ser menor que 4, por lo que el valor mínimo es 4.

Para el segundo ejemplo, no existe una matriz buena de tamaño 1, por lo que se imprime $-1$.

El XOR bit a bit $x \oplus y$ de enteros no negativos $x, y$ se define de la siguiente manera:

• En la representación binaria de $x \oplus y$, el dígito en la posición $2^k$ ($k \geq 0$) es 1 si y solo si exactamente uno de los dígitos en la posición $2^k$ en las representaciones binarias de $x$ e $y$ es 1; de lo contrario, es 0.

Por ejemplo, $3 \oplus 5 = 6$ (en binario, $011 \oplus 101 = 110$).