問題文

kencho 君は $N$ という数とグリッドが大好きです。

kencho 君の家は、正方形の小部屋が $N$ 行 $N$ 列に並んだ間取りをしており、上から $i$ 行目、左から $j$ 列目の小部屋には $A_{i, j}$ 個の家具があります。

初めはこの家に満足していた kencho 君でしたが、部屋の数や各部屋にある家具の個数を、大好きな $N$ にちなんだものにしたくなりました。そこで、隣り合う小部屋の間の壁を一部取り壊し、小部屋をまとめて部屋を作ることにしました。元の各小部屋は分割されることなく、ちょうど $1$ つの部屋に属します。

kencho 君は、以下の条件を全て満たす間取りを作ろうとしています。

• 部屋の数がちょうど $N$ 個である
• 各部屋は $1$ つ以上の小部屋からなり、連結である
• 各部屋にある家具の合計数が $N$ の倍数である

ここで、部屋が連結であるとは、同じ部屋に属する任意の $2$ つの小部屋について、一方から他方まで、同じ部屋に属する小部屋のみを上下左右に辿って移動できることをいいます。

また、家具は全て床に強固に接着されており、動かすことはできません。

どのような間取りにすることで条件を満たすことができるか、kencho 君に教えてあげてください。条件を満たす間取りが存在しない場合は -1 を出力してください。

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

制約

• 入力は全て整数
• $1 \leq T \leq 10^5$
• $2 \leq N \leq 1000$
• $1 \leq A_{i, j} \leq N$
• $1$ 個の入力ファイルにおける $N^2$ の総和は $10^6$ を超えない

入力

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

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

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

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

出力

各ケースに対し、条件を満たす間取りが存在する場合は、以下の形式でその一例を出力してください。

作った $N$ 個の部屋に $1$ から $N$ までの番号を重複なく付けてください。$B_{i, j}$ は、上から $i$ 行目、左から $j$ 列目の小部屋が属する部屋の番号を表します。

$1 \leq B_{i, j} \leq N$ を満たし、各部屋が連結である必要があることに注意してください。また、$1$ 以上 $N$ 以下の各整数 $k$ について $B_{i, j} = k$ となる $(i, j)$ が $1$ つ以上存在する必要があります (サンプル $1$ も参考にしてください)。

$B_{1, 1}\ B_{1, 2}\ \ldots\ B_{1, N}$
$B_{2, 1}\ B_{2, 2}\ \ldots\ B_{2, N}$
$\vdots$
$B_{N, 1}\ B_{N, 2}\ \ldots\ B_{N, N}$

条件を満たす間取りが存在しない場合は -1 を出力してください。

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

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

2
3
2 1 1
3 2 2
1 1 2
2
1 2
1 1

出力

1 1 2
1 3 2
3 3 3
-1

最初のテストケースについて説明します。

新しい間取りにおいて、部屋 $1$ には $6$ 個、部屋 $2$ には $3$ 個、部屋 $3$ には $6$ 個の家具があり、全て $3$ の倍数であるため正答となります。

部屋の分かれ方と家具の配置は次の図の通りです。

以下の出力例は、部屋 $1$ が複数箇所に分かれており連結でないため、不正解となります。

1 3 3
2 1 3
1 1 3

以下の出力例は、部屋 $2$ に属する領域が存在せず、部屋がちょうど $N$ 個という条件に反するため、不正解となります。

1 3 3
1 1 3
1 1 3