配点 : $300$ 点

問題文

$H \times W$ のマス目で表されるキャンバスがあり、上から $i$ $(1 \leq i \leq H)$ 行目、左から $j$ $(1 \leq j \leq W)$ 列目のマスを $(i, j)$ と表します。

最初、マス $(i, j)$ の状態は以下のようになっています。

• $c_{i, j}=$1 のとき：色 1 で塗られている
• $c_{i, j}=$2 のとき：色 2 で塗られている
• $c_{i, j}=$3 のとき：色 3 で塗られている
• $c_{i, j}=$4 のとき：色 4 で塗られている
• $c_{i, j}=$5 のとき：色 5 で塗られている
• $c_{i, j}=$. のとき：まだ塗られていない

上下左右に隣り合うマスが同じ色にならないように、まだ塗られていないマスを色 1, 2, 3, 4, 5 のいずれかで塗る方法を 1 つ構成してください。ただし、既に塗られたマスを別の色で塗り替えることはできません。

制約

• $1 \leq H, W \leq 700$
• $c_{i, j}$ は 1、2、3、4、5、. のいずれか
• まだ塗られていないマスが 1 つ以上存在する
• 条件を満たす塗り方は必ず 1 つ以上存在する

入力

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

$H$ $W$

$c_{1, 1}$$c_{1, 2}$$\ldots$$c_{1, W}$

$c_{2, 1}$$c_{2, 2}$$\ldots$$c_{2, W}$

$:$

$c_{H, 1}$$c_{H, 2}$$\ldots$$c_{H, W}$

出力

マスの塗り方を以下の形式で出力してください。

ただし、$d_{i, j}$ はすべてのマスを塗り終わった後のマス $(i, j)$ の色とします。（1、2、3、4、5 のいずれかでなければなりません）

$d_{1, 1}$$d_{1, 2}$$\ldots$$d_{1, W}$

$d_{2, 1}$$d_{2, 2}$$\ldots$$d_{2, W}$

$:$

$d_{H, 1}$$d_{H, 2}$$\ldots$$d_{H, W}$

条件を満たす塗り方が複数存在する場合、そのうちどれを出力しても構いません。

3 3
...
...
...

132
313
541

出力例 1 は、以下の塗り方に対応しています。

5 7
1.2.3.4
.5.1.2.
3.4.5.1
.2.3.4.
5.1.2.3

1425314
2531425
3142531
4253142
5314253

出力例 2 は、以下の塗り方に対応しています。

1 1
.

4