サイズ $N$ の「良い行列」とは、各行、各列、および両方の対角線の総 XOR 和が 0 となるような、正の整数の $N \times N$ 行列のことである。

より正確には、$N \times N$ 行列 $A$ がサイズ $N$ の良い行列であるとは、以下のすべての条件を満たすものをいう。ここで、$x \oplus y$ は $x$ と $y$ のビット単位の XOR を表し、$\bigoplus_{i=1}^{N} a_i = a_1 \oplus \dots \oplus a_N$ とする。

• $A_{i,j}$ ($1 \le i, j \le N$) は正の整数である。
• 各 $i = 1, 2, \dots, N$ について、$\bigoplus_{j=1}^{N} A_{i,j} = 0$
• 各 $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$

正の整数 $N$ が与えられる。サイズ $N$ のすべての良い行列の中で、全要素の総和 $\sum_{1 \le i,j \le N} A_{i,j}$ が最小となるものを出力せよ。 サイズ $N$ の良い行列が存在しない場合は、その旨を報告せよ。

入力

入力は単一の整数 $N$ からなる。($1 \le N \le 2 \times 10^3$)

出力

サイズ $N$ の良い行列が存在しない場合は、1行に -1 を出力せよ。 存在する場合は、1行目に最小の総和を出力せよ。 続いて、$N$ 行にわたって行列 $A$ を出力せよ。各行の要素はスペースで区切ること。すなわち、$i+1$ 行目には行列 $A$ の第 $i$ 行の要素をスペース区切りで出力すること。 複数の解が存在する場合は、そのうちのどれを出力してもよい。

入出力例

入力 1

2

出力 1

4
1 1
1 1

入力 2

1

出力 2

-1

注記

最初の例では、各行、各列、および両方の対角線の総 XOR 和が 0 となっており、良い行列の条件を満たしている。また、サイズ 2 のすべての良い行列の中で、全要素の総和を 4 未満にすることはできないため、最小値は 4 である。

2番目の例では、サイズ 1 の良い行列は存在しないため、-1 を出力する。

非負整数 $x, y$ のビット単位の XOR $x \oplus y$ は以下のように定義される。

• $x \oplus y$ の二進表現において、$2^k$ ($k \ge 0$) の位の数字は、$x$ と $y$ の二進表現における $2^k$ の位の数字のうち、ちょうど一方が 1 である場合に 1 となり、それ以外の場合は 0 となる。

例えば、$3 \oplus 5 = 6$ である（二進数では $011 \oplus 101 = 110$）。