Gott fylki af stærð $N$ er $N \times N$ fylki af jákvæðum heiltölum þannig að heildar-XOR hverrar línu, hvers dálks og beggja hornalína sé $0$.

Nákvæmar tiltekið kallast $N \times N$ fylki $A$ gott fylki af stærð $N$ ef það uppfyllir öll eftirfarandi skilyrði. Hér táknar $x \oplus y$ bitavísað XOR af $x$ og $y$, og $\bigoplus_{i=1}^N a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \le i, j \le N$) er jákvæð heiltala.
• Fyrir hvert $i = 1, 2, \dots, N$ gildir $\bigoplus_{j=1}^N A_{i,j} = 0$.
• Fyrir hvert $j = 1, 2, \dots, N$ gildir $\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$.

Jákvæð heiltala $N$ er gefin.

Meðal allra góðra fylkja af stærð $N$, skrifaðu út eitt þar sem heildarsumma allra staka, $\sum_{1 \le i, j \le N} A_{i,j}$, er í lágmarki.

Ef ekkert gott fylki af stærð $N$ er til, láttu vita af því.

Inntak

Inntakið samanstendur af einni heiltölu $N$. ($1 \le N \le 2 \times 10^3$)

Úttak

Ef ekkert gott fylki af stærð $N$ er til, prentaðu $-1$ á stakri línu.

Ef það er til, prentaðu minnstu mögulegu heildarsummu allra staka á fyrstu línuna.

Prentaðu síðan fylkið $A$ á næstu $N$ línum, þar sem stökin eru aðskilin með bilum. Það er, $(i+1)$-ta línan á að innihalda stökin í $i$-tu línu fylkisins $A$, aðskilin með bilum.

Ef fleiri en ein lausn er til má prenta hverja sem er þeirra.

Dæmi

Dæmi um inntak 1

2

Dæmi um úttak 1

4
1 1
1 1

Dæmi um inntak 2

1

Dæmi um úttak 2

-1

Athugasemd

Í fyrra dæminu er heildar-XOR hverrar línu, hvers dálks og beggja hornalína $0$, þannig að það uppfyllir skilyrðin fyrir gott fylki. Einnig, meðal allra góðra fylkja af stærð $2$ er ekki hægt að gera heildarsummu allra staka minni en $4$, svo lágmarksgildið er $4$.

Í seinna dæminu er ekkert gott fylki af stærð $1$ til, svo prentaðu $-1$.

Bitavísað XOR $x \oplus y$ af óneikvæðum heiltölum $x, y$ er skilgreint sem hér segir.

• Í tvíundarframsetningu $x \oplus y$ er tölustafurinn í sæti $2^k$ ($k \ge 0$) jafn $1$ ef og aðeins ef nákvæmlega annar tölustafanna í sæti $2^k$ í tvíundarframsetningum $x$ og $y$ er $1$; annars er hann $0$.

Til dæmis er $3 \oplus 5 = 6$ (í tvíundarkerfi, $011 \oplus 101 = 110$).