ストーリー

天才ハッカーのあなたは、敵のロボットをハッキングして秘密の画像データを手に入れました。
しかし、画像データには軽い二次元畳み込み処理が施してあった上に、セキュリティを通過した時に画素の順番がランダムに入れ替わってしまったことに気付きました。
元の画像データを一意に復元することは難しくなってしまいましたが、それでも元の画像として考えられる例を作成することで分かることがあるかもしれません。
元の画像データの一例を構築するプログラムを作成してください。

問題文

$N \times N$ 行列 $A$ があります。行列 $A$ の各要素は非負整数であることが分かっています。

さて、次のように $(N-1) \times (N-1)$ 行列 $B$ を定義します。 $$ B_{i,j} = A_{i, j} + A_{i, j+1} + A_{i+1, j} + A_{i+1, j+1} $$ $B$ の $(N-1)^2$ 個の要素をランダムな順番に並べて得られる配列 $C$ が与えられるので、$A$ として考えられる行列の一例を求めてください。
そのような行列が存在しない場合はその旨を報告してください。

$T$ 個のテストケースが与えられるため、それぞれに解答してください。

制約

• 入力は全て整数
• $1 \leq T \leq 10^4$
• $2 \leq N \leq 700$
• $0 \leq C_i \leq 10^6 - 1$
• $1$ 個の入力ファイルにおける $N^2$ の総和は $5 \times 10^5$ を超えない

入力

入力は以下の形式で標準入力から与えられる。ここで、$case_i$ は $i$ 番目のケースを意味する。

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各テストケースは以下の形式で与えられる。

$N$
$C_1\ C_2\ \cdots\ C_{(N-1)^2}$

出力

各ケースに対し、$A$ として考えられる行列が存在しない場合は -1 を、存在する場合は以下の形式でその一例を出力してください。

$A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, N}$
$A_{2, 1}\ A_{2, 2}\ \cdots\ A_{2, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \cdots\ A_{N, N}$

各ケースに対する出力の最後に改行してください。

サンプル

3
3
2 0 2 5
2
9
4
3 1 4 1 5 9 2 6 5

2 0 1
0 0 1
0 0 4
2 0
2 5
1 1 0 0
1 0 0 1
2 2 0 4
1 4 0 0