ストーリー

札幌から網走までの移動距離と、大阪から広島までの移動距離はほぼ同じです（諸説あり）。

ところで kencho 君は、グリッドグラフ上でドライブがしたくなりました。毎日走りたい距離を決めた後に、条件を満たす始点と終点の組を探して走る事にしましたが、そのような組が複数存在するとどこを走るか迷ってしまうことに気付きました。なお、kencho 君はカーナビを使うため必ず最短経路上を走ります。

kencho 君が迷わずに済むグリッドグラフを作ってあげましょう。

問題文

頂点が $N$ 行 $N$ 列に並んだ無向グリッドグラフ $G$ があります。$1 \leq i, j \leq N$ について $G$ の上から $i$ 行目、左から $j$ 列目の頂点の番号は $(i - 1) N + j$ です。

あなたは $G$ の各辺について $1$ 以上 $3 \times 10^5$ 以下の整数を選んで重みを定めることができます。

経路の長さを、その経路に含まれる辺の重みの総和とします。また、$2$ 頂点間の最短距離を、その $2$ 頂点を結ぶ経路の長さの最小値とします。

異なる $2$ 頂点の順序を区別しないペアは、全部で $\frac{N^2(N^2-1)}{2}$ 通りあります。これらのペアについて、$2$ 頂点間の最短距離が全て異なるように、各辺の重みを定めてください。

より厳密には、$1 \leq i \lt j \leq N^2$ について、$G$ の頂点 $i$ と $j$ の間の最短距離を $d_{i,j}$ とするとき、$(i_1, j_1) \neq (i_2, j_2) \Rightarrow d_{i_1,j_1} \neq d_{i_2,j_2}$ が成り立つようにしてください。

同じ $2$ 頂点を結ぶ最短経路が複数存在しても構いません。

条件を満たす辺重みの定め方が存在しない場合は -1 を出力してください。

制約

• 入力は全て整数
• $2 \leq N \leq 50$

入力

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

$N$

出力

各辺の重みを以下の形式で出力してください。ただし、$v_{i, j}$ は頂点 $(i-1)N + j$ と頂点 $iN + j$ を結ぶ縦向きの辺の重み、$h_{i, j}$ は頂点 $(i-1)N + j$ と頂点 $(i-1)N + j + 1$ を結ぶ横向きの辺の重みを表します。

$v_{1,1}\ v_{1,2}\ \ldots\ v_{1,N}$
$v_{2,1}\ v_{2,2}\ \ldots\ v_{2,N}$
$\vdots$
$v_{N-1,1}\ v_{N-1,2}\ \ldots\ v_{N-1,N}$
$h_{1,1}\ h_{1,2}\ \ldots\ h_{1,N-1}$
$h_{2,1}\ h_{2,2}\ \ldots\ h_{2,N-1}$
$\vdots$
$h_{N,1}\ h_{N,2}\ \ldots\ h_{N,N-1}$

条件を満たす辺重みの定め方が存在しない場合は -1 を出力してください。

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

ビジュアライザ

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

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

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

サンプル

サンプル1

入力

2

出力

1 3
6
4

各頂点ペア間の最短距離は以下の通りで、全て異なります。

• 頂点 $1$ と $2$ の間の最短距離は $6$
• 頂点 $1$ と $3$ の間の最短距離は $1$
• 頂点 $1$ と $4$ の間の最短距離は $5$
• 頂点 $2$ と $3$ の間の最短距離は $7$
• 頂点 $2$ と $4$ の間の最短距離は $3$
• 頂点 $3$ と $4$ の間の最短距離は $4$