Une matrice « bonne » de taille $N$ est une matrice $N \times N$ d'entiers positifs telle que le XOR total de chaque ligne, de chaque colonne et des deux diagonales soit égal à 0.

Plus précisément, une matrice $A$ de taille $N \times N$ est appelée une bonne matrice de taille $N$ si elle satisfait toutes les conditions suivantes. Ici, $x \oplus y$ désigne le XOR bit à bit de $x$ et $y$, et $\bigoplus_{i=1}^{N} a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \leq i, j \leq N$) est un entier positif.
• Pour chaque $i = 1, 2, \dots, N$, $\bigoplus_{j=1}^{N} A_{i,j} = 0$.
• Pour chaque $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$.

Un entier positif $N$ est donné. Parmi toutes les bonnes matrices de taille $N$, affichez-en une dont la somme totale de tous les éléments, $\sum_{1 \leq i,j \leq N} A_{i,j}$, est minimale. Si aucune bonne matrice de taille $N$ n'existe, signalez-le.

Entrée

L'entrée consiste en un seul entier $N$. ($1 \leq N \leq 2 \times 10^3$)

Sortie

Si aucune bonne matrice de taille $N$ n'existe, affichez -1 sur une seule ligne. Si elle existe, affichez la somme totale minimale possible de tous les éléments sur la première ligne. Ensuite, affichez la matrice $A$ sur les $N$ lignes suivantes, avec les éléments séparés par des espaces. C'est-à-dire que la $(i+1)$-ième ligne doit contenir les éléments de la $i$-ième ligne de la matrice $A$, séparés par des espaces. S'il existe plusieurs solutions, n'importe laquelle peut être affichée.

Exemples

Entrée 1

2

Sortie 1

4
1 1
1 1

Entrée 2

1

Sortie 2

-1

Note

Pour le premier exemple, le XOR total de chaque ligne, chaque colonne et des deux diagonales est 0, donc cela satisfait les conditions d'une bonne matrice. De plus, parmi toutes les bonnes matrices de taille 2, la somme totale de tous les éléments ne peut pas être inférieure à 4, donc la valeur minimale est 4.

Pour le second exemple, il n'existe aucune bonne matrice de taille 1, donc affichez -1.