题目描述

我们有一个画布，表示为一个 $H \times W$ 的网格。$(i, j)$ 表示网格中从上往下数第 $i$ 行（$1 \leq i \leq H$）从左往右数第 $j$ 列（$1 \leq j \leq W$）的方块。

初始时，$(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 \leq H, W \leq 700$
• $c_{i, j}$ 可能是 1、2、3、4、5 或 .。
• 至少有一个方块没有涂色。
• 存在至少一种满足条件的涂色方法。

输入

从标准输入读取输入数据，具体格式如下：

$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}$

如果存在多种满足条件的涂色方法，你可以任选其中之一进行输出。

示例输入1

3 3
...
...
...

示例输出1

132
313
541

示例输出1 对应以下涂色方式：

示例输入2

5 7
1.2.3.4
.5.1.2.
3.4.5.1
.2.3.4.
5.1.2.3

示例输出2

1425314
2531425
3142531
4253142
5314253

示例输出2 对应以下涂色方式：

示例输入3

1 1
.

示例输出3

4