#P18013. Building a Reactor

Building a Reactor

Building a Reactor

有一个 n×mn\times m 的网格。有些格子是承重墙,不能放置其他物品。每个其余格子可以放置一根燃料棒、一个冷却元件,或者留空。

每根燃料棒必须与至少一个冷却元件相邻,这里的相邻指两个格子共用一条边。

请构造一种合法摆放方案,使燃料棒的总数最多。

输入格式

第一行两个整数 n,mn,m,分别表示网格的高度和宽度。

接下来 nn 行,每行一个长度为 mm 的字符串。. 表示空闲格子,# 表示承重墙。

输出格式

输出 nn 行,每行 mm 个字符,描述最优方案:

  • #:原来的承重墙;
  • 0:燃料棒;
  • 1:冷却元件;
  • .:仍然留空的格子。

不得改变承重墙的位置。若有多种最优方案,输出任意一种。

数据范围

1≤n≤121\le n\le12,1≤m≤301\le m\le30。

样例 1

输入

6 9
.........
.........
....#....
....#....
.........
.........

输出

001000100
100010001
0010#0100
0010#0100
100010001
001000100