数独は一般に $n$ 個の $\sqrt{n} \times \sqrt{n}$ のブロックからなる $n \times n$ のグリッドで構成されます。

各行および各列の数字は $1 \sim n$ を含み、欠けていたり重複していたりしてはいけません。各ブロック（太線で囲まれた $\sqrt{n} \times \sqrt{n}$ の領域）の数字も $1 \sim n$ を含み、欠けていたり重複していたりしてはいけません。完成させるにはこれら3つの条件を同時に満たす必要があります。

図は $n=9$ の数独の例です。

不完全な数独の盤面が与えられます。任意の数の数字を補い、完成後の数独がちょうど2つの解を持つ、すなわち唯一の2解を持つようにしてください。また、そのような補い方のうち、対応する2つの解の差異が最大となるものを求めてください。ここで、差異とは2つの解をセルごとに比較した際、数字が異なるセルの個数と定義します。

同時に、数独内の任意の2つの位置について、2つの解の1つ目の位置の数字を $x_1, x_2$、2つ目の位置の数字を $y_1, y_2$ としたとき、$x_1 \neq x_2, y_1 \neq y_2, x_1 \neq y_2, x_1 \neq y_1$ が同時に成り立つことはありません。

入力形式

1行目に数独のサイズ $n$ が与えられます。

続く $n$ 行に $n$ 個の数字 ${a_i}_j$ が与えられ、不完全な数独の盤面を表します。$0$ は数字が埋まっていない場所を表します。

出力形式

$n$ 行にわたり、補完後の盤面を出力してください。複数の補い方で2つの解の差異が最大となる場合、そのうちのいずれかを出力すれば正解となります。

入出力例

入力 1

4
3 0 0 0
0 0 0 0
0 3 0 0
0 0 0 3

出力 1

3 0 0 0
0 0 0 2
0 3 0 0
2 0 0 3

注記

サンプル出力に対応する2つの解は以下の通りです。

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

および

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

これらを比較すると差異は $8$ となります。これがこの盤面における最大差異 $8$ を達成する一つの方法です。

制約

サブタスク 1 の制限時間は 2 秒、その他の制限時間は 30 秒です。

すべてのデータにおいて：$a_{i,j} \in [0, n]$ であり、与えられた不完全な数独には少なくとも1つ、唯一の2解を持つような補完方法が存在することが保証されます。