En god matrise av størrelse $N$ er en $N \times N$-matrise av positive heltall slik at den totale XOR-verdien av hver rad, hver kolonne og begge diagonalene er $0$.

Mer presist kalles en $N \times N$-matrise $A$ en god matrise av størrelse $N$ hvis den oppfyller alle de følgende betingelsene. Her betegner $x \oplus y$ den bitvise XOR-verdien av $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 et positivt heltall.
• For hver $i = 1, 2, \dots, N$ gjelder $\bigoplus_{j=1}^N A_{i,j} = 0$.
• For hver $j = 1, 2, \dots, N$ gjelder $\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$.

Et positivt heltall $N$ er gitt.

Blant alle gode matriser av størrelse $N$, skriv ut en der den totale summen av alle elementene, $\sum_{1 \le i, j \le N} A_{i,j}$, er minst mulig.

Hvis det ikke finnes noen god matrise av størrelse $N$, rapporter dette.

Inndata

Inndataene består av et enkelt heltall $N$. ($1 \le N \le 2 \times 10^3$)

Utdata

Hvis det ikke finnes noen god matrise av størrelse $N$, skriv ut $-1$ på en enkelt linje.

Hvis det finnes en, skriv ut den minste mulige totale summen av alle elementene på den første linjen.

Skriv deretter ut matrisen $A$ på de påfølgende $N$ linjene, med elementene adskilt med mellomrom. Det vil si at den $(i+1)$-te linjen skal inneholde elementene i den $i$-te raden av matrisen $A$, adskilt med mellomrom.

Hvis det finnes flere løsninger, kan hvilken som helst av dem skrives ut.

Eksempler

Eksempelinndata 1

2

Eksempelutdata 1

4
1 1
1 1

Eksempelinndata 2

1

Eksempelutdata 2

-1

Forklaring

For det første eksempelet er den totale XOR-verdien av hver rad, hver kolonne og begge diagonalene $0$, så den oppfyller betingelsene for en god matrise. Blant alle gode matriser av størrelse $2$ kan heller ikke den totale summen av alle elementene gjøres mindre enn $4$, så minimumsverdien er $4$.

For det andre eksempelet finnes det ingen god matrise av størrelse $1$, så skriv ut $-1$.

Den bitvise XOR-verdien $x \oplus y$ for ikke-negative heltall $x, y$ er definert som følger.

• I den binære representasjonen av $x \oplus y$ er sifferet på $2^k$-plassen ($k \ge 0$) lik $1$ hvis og bare hvis nøyaktig ett av sifrene på $2^k$-plassen i de binære representasjonene av $x$ og $y$ er $1$; ellers er det $0$.

For eksempel er $3 \oplus 5 = 6$ (i binær form, $011 \oplus 101 = 110$).