問題文

長さ $N$ の数列 $R = (R_1, R_2, \ldots, R_N)$ と $C = (C_1, C_2, \ldots, C_N)$ が与えられます。$R$ は $1, 2, \ldots, N$ の順列です。

$N \times N$ グリッドの各マスに、$1$ 以上 $N$ 以下の整数を書き込みます。以下の条件を全て満たすような書き込み方の一例を求めてください。存在しない場合は -1 を出力してください。

• $1 \leq i \leq N$ について、$i$ 行目に書かれた $N$ 個の整数の最頻値は $R_i$ のみである
• $1 \leq i \leq N$ について、$i$ 列目に書かれた $N$ 個の整数の最頻値は $C_i$ のみである

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

制約

• 入力は全て整数
• $1 \leq T \leq 10^5$
• $1 \leq N \leq 1000$
• $R$ は $1, 2, \ldots, N$ の順列
• $1 \leq C_i \leq N$
• $1$ 個の入力ファイルにおける $N^2$ の総和は $10^6$ を超えない

入力

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

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

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

$N$
$R_1\ R_2\ \ldots\ R_N$
$C_1\ C_2\ \ldots\ C_N$

出力

各ケースに対し、条件を満たす書き込み方が存在しない場合は -1 を、存在する場合は以下の形式でその一例を出力してください。ただし、グリッドの上から $i$ 行目、左から $j$ 列目のマスに書き込む整数を $A_{i, j}$ と表します。

$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}$

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

ビジュアライザ

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

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

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

サンプル

サンプル1

入力

2
4
2 3 1 4
3 2 4 1
2
1 2
2 1

出力

2 2 1 3
3 3 3 1
1 2 4 1
3 4 4 1
-1

各行・各列ともに、与えられた値が唯一の最頻値となる必要があることに注意してください。

$1$ 番目のテストケースに対する出力例が表すグリッドと各行・各列の最頻値は下図のようになります。

このテストケースは部分点ケースに含まれます。

1
3
2 1 3
3 3 1

2 3 2
3 1 1
3 3 1