建造一个可靠且高效的反应堆包含许多阶段，你的任务是帮助设计这样一个反应堆。

反应堆的框架是一个大小为 $n \times m$ 的网格。其中一些格子包含承重墙，用于增强结构强度，不能用于其他任何目的。其余的格子可以填充燃料棒和冷却元件，每个格子最多只能填充一个。

根据安全规定，每个燃料棒必须与至少一个冷却元件相邻。形式化地，它们所在的格子必须共享一条公共边。

设计中的燃料棒越多，反应堆能提取的能量就越多。你的任务是在遵守所有要求的前提下，找到一种包含最多燃料棒数量的任意配置。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 12$, $1 \le m \le 30$)，表示反应堆框架的高度和宽度。

接下来的 $n$ 行，每行包含 $m$ 个字符，描述反应堆的格子。字符 . 对应一个空闲格子，而字符 # 对应一面承重墙。

输出格式

输出 $n$ 行，每行 $m$ 个字符（共 $nm$ 个字符），表示反应堆元件的最优排列。字符可以取以下值：

• #：如果该格子是承重墙；
• 0：如果你在该格子中放置了燃料棒；
• 1：如果你在该格子中放置了冷却元件；
• .：如果该格子保持空白。

如果有多个最优解，输出其中任意一个。

样例

输入样例 1

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

输出样例 1

001000100
100010001
0010#0100
0010#0100
100010001
001000100