Kokoa $N$ oleva hyvä matriisi on positiivisista kokonaisluvuista koostuva $N \times N$ -matriisi, jonka jokaisen rivin, jokaisen sarakkeen ja molempien lävistäjien kokonais-XOR on $0$.

Tarkemmin sanottuna $N \times N$ -matriisia $A$ kutsutaan kokoa $N$ olevaksi hyväksi matriisiksi, jos se täyttää kaikki seuraavat ehdot. Tässä $x \oplus y$ tarkoittaa lukujen $x$ ja $y$ bittikohtaista XOR-operaatiota ja $\bigoplus_{i=1}^N a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \le i, j \le N$) on positiivinen kokonaisluku.
• Jokaisella $i = 1, 2, \dots, N$ pätee $\bigoplus_{j=1}^N A_{i,j} = 0$.
• Jokaisella $j = 1, 2, \dots, N$ pätee $\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$.

Annetaan positiivinen kokonaisluku $N$.

Tulosta kaikista kokoa $N$ olevista hyvistä matriiseista sellainen, jonka kaikkien alkioiden kokonaissumma $\sum_{1 \le i, j \le N} A_{i,j}$ on pienin mahdollinen.

Jos kokoa $N$ olevaa hyvää matriisia ei ole olemassa, ilmoita siitä.

Syöte

Syöte koostuu yhdestä kokonaisluvusta $N$. ($1 \le N \le 2 \times 10^3$)

Tuloste

Jos kokoa $N$ olevaa hyvää matriisia ei ole olemassa, tulosta $-1$ omalle rivilleen.

Jos sellainen on olemassa, tulosta ensimmäiselle riville kaikkien alkioiden pienin mahdollinen kokonaissumma.

Tulosta sitten matriisi $A$ seuraaville $N$ riville alkioiden ollessa välilyönnein erotettuja. Toisin sanoen rivin $(i+1)$ tulee sisältää matriisin $A$ rivin $i$ alkiot välilyönnein erotettuina.

Jos ratkaisuja on useita, mikä tahansa niistä voidaan tulostaa.

Esimerkit

Esimerkkisyöte 1

2

Esimerkkituloste 1

4
1 1
1 1

Esimerkkisyöte 2

1

Esimerkkituloste 2

-1

Huomautus

Ensimmäisessä esimerkissä jokaisen rivin, jokaisen sarakkeen ja molempien lävistäjien kokonais-XOR on $0$, joten se täyttää hyvän matriisin ehdot. Lisäksi kaikista kokoa $2$ olevista hyvistä matriiseista kaikkien alkioiden kokonaissummaa ei voida saada pienemmäksi kuin $4$, joten pienin arvo on $4$.

Toisessa esimerkissä kokoa $1$ olevaa hyvää matriisia ei ole olemassa, joten tulosta $-1$.

Ei-negatiivisten kokonaislukujen $x, y$ bittikohtainen XOR $x \oplus y$ määritellään seuraavasti.

• Luvun $x \oplus y$ binääriesityksessä kohdan $2^k$ ($k \ge 0$) bitti on $1$ täsmälleen silloin, kun tasan toinen lukujen $x$ ja $y$ binääriesitysten kohdan $2^k$ biteistä on $1$; muuten se on $0$.

Esimerkiksi $3 \oplus 5 = 6$ (binäärinä $011 \oplus 101 = 110$).