Eine gute Matrix der Größe $N$ ist eine $N \times N$-Matrix aus positiven ganzen Zahlen, sodass das Gesamt-XOR jeder Zeile, jeder Spalte und beider Diagonalen gleich $0$ ist.

Genauer gesagt heißt eine $N \times N$-Matrix $A$ eine gute Matrix der Größe $N$, wenn sie alle folgenden Bedingungen erfüllt. Hierbei bezeichnet $x \oplus y$ das bitweise XOR von $x$ und $y$, und es gilt $\bigoplus_{i=1}^N a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \le i, j \le N$) ist eine positive ganze Zahl.
• Für jedes $i = 1, 2, \dots, N$ gilt $\bigoplus_{j=1}^N A_{i,j} = 0$.
• Für jedes $j = 1, 2, \dots, N$ gilt $\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$.

Eine positive ganze Zahl $N$ ist gegeben.

Gib unter allen guten Matrizen der Größe $N$ eine aus, deren Gesamtsumme aller Elemente, $\sum_{1 \le i, j \le N} A_{i,j}$, minimal ist.

Falls keine gute Matrix der Größe $N$ existiert, melde dies.

Eingabe

Die Eingabe besteht aus einer einzigen ganzen Zahl $N$. ($1 \le N \le 2 \times 10^3$)

Ausgabe

Falls keine gute Matrix der Größe $N$ existiert, gib $-1$ in einer einzelnen Zeile aus.

Falls eine existiert, gib in der ersten Zeile die kleinstmögliche Gesamtsumme aller Elemente aus.

Gib anschließend die Matrix $A$ in den folgenden $N$ Zeilen aus, wobei die Elemente durch Leerzeichen getrennt sind. Das heißt, die $(i+1)$-te Zeile soll die Elemente der $i$-ten Zeile der Matrix $A$, getrennt durch Leerzeichen, enthalten.

Falls es mehrere Lösungen gibt, kann eine beliebige davon ausgegeben werden.

Beispiele

Beispieleingabe 1

2

Beispielausgabe 1

4
1 1
1 1

Beispieleingabe 2

1

Beispielausgabe 2

-1

Hinweis

Für das erste Beispiel ist das Gesamt-XOR jeder Zeile, jeder Spalte und beider Diagonalen gleich $0$, sodass die Bedingungen für eine gute Matrix erfüllt sind. Außerdem kann unter allen guten Matrizen der Größe $2$ die Gesamtsumme aller Elemente nicht kleiner als $4$ gemacht werden, sodass das Minimum $4$ beträgt.

Für das zweite Beispiel gibt es keine gute Matrix der Größe $1$, gib also $-1$ aus.

Das bitweise XOR $x \oplus y$ nichtnegativer ganzer Zahlen $x, y$ ist wie folgt definiert.

• In der Binärdarstellung von $x \oplus y$ ist die Ziffer an der Stelle $2^k$ ($k \ge 0$) genau dann $1$, wenn genau eine der Ziffern an der Stelle $2^k$ in den Binärdarstellungen von $x$ und $y$ gleich $1$ ist; andernfalls ist sie $0$.

Beispielsweise gilt $3 \oplus 5 = 6$ (binär $011 \oplus 101 = 110$).