"Dobra macierz" rozmiaru $N$ to macierz $N \times N$ składająca się z dodatnich liczb całkowitych, taka że suma XOR każdego wiersza, każdej kolumny oraz obu przekątnych wynosi 0.

Dokładniej, macierz $A$ rozmiaru $N \times N$ nazywamy dobrą macierzą rozmiaru $N$, jeśli spełnia wszystkie poniższe warunki. Tutaj $x \oplus y$ oznacza bitową operację XOR liczb $x$ i $y$, a $\bigoplus_{i=1}^{N} a_i = a_1 \oplus \dots \oplus a_N$.

• $A_{i,j}$ ($1 \le i, j \le N$) jest dodatnią liczbą całkowitą.
• Dla każdego $i = 1, 2, \dots, N$, $\bigoplus_{j=1}^{N} A_{i,j} = 0$.
• Dla każdego $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$.

Dana jest dodatnia liczba całkowita $N$. Spośród wszystkich dobrych macierzy rozmiaru $N$ należy wypisać taką, której całkowita suma wszystkich elementów, $\sum_{1 \le i,j \le N} A_{i,j}$, jest minimalna.

Jeśli nie istnieje żadna dobra macierz rozmiaru $N$, należy to zgłosić.

Wejście

Wejście składa się z pojedynczej liczby całkowitej $N$ ($1 \le N \le 2 \times 10^3$).

Wyjście

Jeśli dobra macierz rozmiaru $N$ nie istnieje, wypisz $-1$ w pojedynczej linii.

Jeśli istnieje, wypisz w pierwszej linii minimalną możliwą sumę wszystkich elementów. Następnie wypisz macierz $A$ w $N$ liniach, z elementami oddzielonymi spacjami. Oznacza to, że $(i+1)$-sza linia powinna zawierać elementy $i$-tego wiersza macierzy $A$, oddzielone spacjami.

Jeśli istnieje wiele rozwiązań, można wypisać dowolne z nich.

Przykład

Wejście 1

2

Wyjście 1

4
1 1
1 1

Uwagi

Dla pierwszego przykładu suma XOR każdego wiersza, każdej kolumny i obu przekątnych wynosi 0, więc spełnia on warunki dobrej macierzy. Ponadto, spośród wszystkich dobrych macierzy rozmiaru 2, całkowitej sumy wszystkich elementów nie da się zmniejszyć poniżej 4, więc wartością minimalną jest 4.

Wejście 2

1

Wyjście 2

-1

Uwagi

Dla drugiego przykładu nie istnieje dobra macierz rozmiaru 1, więc wypisujemy $-1$.

Uwagi

Bitowa operacja XOR $x \oplus y$ nieujemnych liczb całkowitych $x, y$ jest zdefiniowana następująco:

• W reprezentacji binarnej $x \oplus y$, cyfra na pozycji $2^k$ ($k \ge 0$) wynosi 1 wtedy i tylko wtedy, gdy dokładnie jedna z cyfr na pozycji $2^k$ w reprezentacjach binarnych $x$ oraz $y$ wynosi 1; w przeciwnym razie wynosi 0.

Na przykład $3 \oplus 5 = 6$ (binarnie $011 \oplus 101 = 110$).