← 返回题目列表

Codeforces · 435/E

E. 特别图

中文机器翻译题面 查看原题

在这个问题中,您将需要处理一个 n × m 的网格图。图的顶点是 n × m 网格的节点。图的边是网格单位正方形的所有边和对角线。

下图显示了一个 3 × 5 的图表。黑线是图形的边缘,彩色圆圈是图形的顶点。将图的顶点绘制在图片上是有原因的:着色是将 3 × 5 图正确的顶点着色为四种颜色。当且仅当每个顶点都被绘制并且没有由边连接的两个顶点被绘制为相同的颜色时,图着色才是正确的。

给定网格图的大小 n × m 及其一些顶点的颜色。找到任何方法如何用 4 种颜色绘制图形的未绘制顶点,以使最终着色成为正确的顶点图着色。如果没有这样正确的顶点着色,就说答案不存在。

输入

第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 1000)。接下来的 n 行中的每一行都由 m 个字符组成 - 给定的图形。每个字符都是“0”、“1”、“2”、“3”、“4”。字符“0”表示对应的顶点未绘制,否则该字符表示该顶点的颜色。

假设所有可用颜色的编号为 1 到 4。

输出

如果无法获得图形的正确顶点着色,请在一行中打印 0。否则打印彩色 n × m 图。以与输入相同的格式打印图表。

如果存在多个答案,则打印其中任何一个。

示例

输入 #1

3 5
10101
00020
01000

输出 #1

13131
42424
31313

输入 #2

2 2
00
00

输出 #2

12
34

输入 #3

2 2
11
00

输出 #3

0

注意

第一个样本的答案如图所示(1 — 绿色,2 — 蓝色,3 — 深蓝色,4 — 粉色)。

在第二个样本中存在 4 个!答案,每个答案都被认为是正确的。

在第三个示例中,两个具有相同颜色的顶点相连。因此无法获得正确的顶点着色。