問題文

kamipeipaa君はスライドパズル(参考)が好きですが魔方陣(参考)も好きです。
$N × N$のスライドパズルの盤面が与えられるので魔方陣を作ってみましょう。

$N × N$ マスの盤上に、$1$ から $N^{2}-1$ までの互いに相異なる整数が書かれた駒が並べられています。
空きマスの上下左右に隣接した駒を、空きマスにスライドして動かすことを繰り返すことができます。
空きマスに$N^{2}$の駒を入れることで完成したものとします。$N^2$の駒は空きマスでさえあればどこにでも置くことができるものとします。

入力

$N$
$A_{1,1}$ $A_{1,2}$ $…$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $…$ $A_{2,N}$
$⋮$
$A_{N,1}$ $A_{N,2}$ $…$ $A_{N,N}$

1行目にスライドパズルのサイズを表す整数$1 \le N \le 50$が与えられます。
$A_{i,j}$は$0$から$N^{2}-1$までの互いに相異なる整数であり、 $0$ は空きマスを表します。

出力

現在の盤面から魔方陣を作ることができるならば1行目に"possible"を出力し、続く$N$行に目標とする魔方陣を出力せよ。
魔方陣のフォーマットは入力と同様に1行に$N$個の要素を空白区切りで出力すればよい。
魔方陣を作ることができないならば"impossible"を出力せよ。

この問題はスペシャルジャッジである。魔方陣の盤面は現在の盤面から作れるものであれば、どれを出力してもよい。

サンプル

3
8 1 6
3 5 7
4 0 2

possible
8 1 6
3 5 7
4 9 2

3
8 1 6
3 0 7
4 5 2

possible
8 1 6
3 5 7
4 9 2

2
0 1
2 3

impossible