問題文

$(N+1) \times N$ のグリッドがあり、上から $i$ 行目、左から $j$ 列目に位置するマスを $(i, j)$ と表すことにします。

また、$(1, 2, \ldots, N)$ の順列 $A = (A_1, A_2, \ldots, A_N)$ と $B = (B_1, B_2, \ldots, B_N)$ が与えられます。

現在、グリッドの上から $1$ 行目には順列 $A$ の内容が、$N+1$ 行目には順列 $B$ の内容が書かれています。

つまり、$i = 1, 2, \ldots, N$ について、マス $(1, i)$ には $A_i$ 、マス $(N+1, i)$ には $B_i$ が書かれています。 その他のマスには何も書かれていません。

何も書かれていない全てのマスに $1$ 以上 $N$ 以下の整数を書き込むことで、$i = 1, 2, \ldots, N$ について、$i$ の書かれたマスの集合全体が $8$ 近傍で連結となるようにできますか？

ただし、「$k$ の書かれたマスの集合全体が $8$ 近傍で連結である」とは、$k$ が書かれたマス同士の任意のペアについて、上下左右斜めに隣接するような $k$ が書かれたマスへの移動を繰り返すことで一方からもう一方へと移動することができることを意味します。

可能であれば整数の書き込み方の一例を求め、不可能であれば -1 を出力してください。

制約

• 入力は全て整数
• $2 \leq N \leq 500$
• $A$ は $1, 2, \ldots, N$ の順列
• $B$ は $1, 2, \ldots, N$ の順列

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1\ A_2\ \ldots\ A_N$
$B_1\ B_2\ \ldots\ B_N$

出力

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

$C_{1, 1}\ C_{1, 2}\ \ldots\ C_{1, N}$
$C_{2, 1}\ C_{2, 2}\ \ldots\ C_{2, N}$
$\vdots$
$C_{N+1, 1}\ C_{N+1, 2}\ \ldots\ C_{N+1, N}$

$i = 1, 2, \ldots, N$ について、$C_{1, i} = A_i, C_{N+1, i} = B_i$ が成り立つ必要があることに注意してください。

最後に改行してください。

ビジュアライザ

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

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

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

サンプル

サンプル1

入力

4
2 1 3 4
3 2 4 1

出力

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

出力例が表すグリッドは下図の通りです。