CF435E.Special Graph

In this problem you will need to deal with an n × m grid graph. The graph's vertices are the nodes of the n × m grid. The graph's edges are all the sides and diagonals of the grid's unit squares.

The figure below shows a 3 × 5 graph. The black lines are the graph's edges, the colored circles are the graph's vertices. The vertices of the graph are painted on the picture for a reason: the coloring is a correct vertex coloring of the 3 × 5 graph into four colors. A graph coloring is correct if and only if each vertex is painted and no two vertices connected by an edge are painted the same color.

You are given the size of the grid graph n × m and the colors of some of its vertices. Find any way how to paint the unpainted vertices of the graph in 4 colors to make the final coloring a correct vertex graph coloring. If there is no such correct vertex coloring, say that the answer doesn't exist.

本题中，你需要处理一个 $n \times m$ 的网格图。该图的顶点为 $n \times m$ 网格的所有格点；该图的边包括所有单位正方形的四条边及其两条对角线。

下图展示了一个 $3 \times 5$ 的网格图：黑色线段表示图的边，彩色圆点表示图的顶点。图中对顶点进行了着色，其原因在于：该着色是 $3 \times 5$ 网格图的一个合法四色顶点着色。所谓图的合法着色，是指每个顶点均被染色，且任意两个由一条边直接相连的顶点颜色互不相同。

给定网格图的尺寸 $n \times m$ 以及其中部分顶点的颜色，请你为所有尚未着色的顶点分配四种颜色之一，使得最终得到的整个图着色是合法的顶点着色。若不存在这样的合法着色，请说明答案不存在。

The first line contains two integers n and m (2 ≤ n, m ≤ 1000). Each of the next n lines consists of m characters — the given graph. Each character is either «0», «1», «2», «3», «4». Character «0» means that the corresponding vertex is unpainted, otherwise the character means the color of the vertex.

Assume that all the available colors are numbered from 1 to 4.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 1000$）。接下来的 $n$ 行，每行包含 $m$ 个字符——表示给定的图。每个字符为 «0»、«1»、«2»、«3» 或 «4» 中的一个。「0」表示对应顶点未着色，其余字符表示该顶点的颜色。

假设所有可用颜色编号为 $1$ 至 $4$。

If there is no way to get correct vertex coloring of the graph, print 0 in a single line. Otherwise print the colored n × m graph. Print the graph in the same format as in the input.

If multiple answers exist, print any of them.

如果无法对图进行正确的顶点着色，则在单独一行中输出 0。否则，输出着色后的 $n \times m$ 图。输出格式需与输入格式相同。

若存在多个可行解，输出任意一个即可。

The answer to the first sample is shown on the picture (1 — green color, 2 — blue, 3 — dark blue, 4 — pink).

In the second sample there exists 4! answers, each of them is considered correct.

In the third sample two vertices with equal colors are connected. So the correct vertex coloring couldn't be obtained.

第一个样例的答案如图所示（1 — 绿色，2 — 蓝色，3 — 深蓝色，4 — 粉色）。

在第二个样例中，存在 $4!$ 种答案，每种均被视为正确。

在第三个样例中，两个颜色相同的顶点相连，因此无法得到正确的顶点着色。