← 返回题目列表

Codeforces · 86/B

B. 俄罗斯方块重温

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

物理学家沃尔喜欢在探索万有理论的间隙玩一款轻松的游戏。

游戏界面由一个 n × m 的矩形游戏场和一个仪表板组成。最初,运动场的一些单元格被填满,而另一些单元格是空的。仪表板包含 2、3、4 和 5 个单元的所有各种连接(我们指的是侧面连接)图形的图像,以及它们的所有旋转和反射。玩家可以从仪表板上复制任何图形并将其放置在比赛场地中仍然空的单元格的任何位置。当然,任何数字都可以根据需要多次使用。

沃尔的目标是以不留任何空白单元格的方式填充整个字段,并且......只是享受一些乐趣。

每个最初为空的单元格都应该恰好填充某个数字的一​​个单元格。每个图形都应该完全位于板内。

在图片中,黑色单元代表字段中最初填充的单元,单色区域代表数字。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 1000) — 相应字段的高度和宽度。接下来的 n 行每行包含 m 个符号。它们以自然的方式表示字段:如果相应的单元格已填充,则第 i 行的第 j 个字符是“#”,而“.”则为“#”。如果它是空的。

输出

如果没有机会赢得比赛,则输出唯一的数字“-1”(不带引号)。否则,按以下格式输出任何由数字填充的字段:每个数字应由一些数字表示,并且彼此接触的数字应由不同的数字表示。每个最初填充的单元格都应该用“#”表示。

示例

输入 #1

2 3
...
#.#

输出 #1

000
#0#

输入 #2

3 3
.#.
...
..#

输出 #2

5#1
511
55#

输入 #3

3 3
...
.##
.#.

输出 #3

-1

输入#4

1 2
##

输出#4

##

注意

在第三个示例中,无法填充没有空邻居的单元格。

在第四个示例中,Woll 不必填写任何内容,因此我们应该从输入中输出该字段。