帕维尔喜欢网格迷宫。网格迷宫是一个 n × m 的矩形迷宫,其中每个单元格要么是空的,要么是一面墙。仅当两个单元格都是空的并且有公共边时,您才可以从一个单元格转到另一个单元格。
Pavel 画了一个网格迷宫,所有空单元格形成一个连接区域。也就是说,您可以从任何空单元格转到任何其他单元格。帕维尔不喜欢他的迷宫的墙太少。他想将恰好 k 个空单元格变成墙壁,以便所有剩余的单元格仍然形成一个连接的区域。帮助他。
输入
第一行包含三个整数n、m、k(1 ≤ n、m ≤ 500、0 ≤ k < s),其中n和m是迷宫的高度和宽度,相应地,k是Pavel想要添加的墙的数量,字母s代表原始迷宫中空单元的数量。
接下来的 n 行每行包含 m 个字符。他们描述了原来的迷宫。如果一行上的字符等于“.”,则相应的单元格是空的,如果该字符等于“#”,则该单元格是一堵墙。
输出
打印 n 行,每行包含 m 个字符:符合 Pavel 要求的新迷宫。将您转换成墙壁的空单元格标记为“X”,其他单元格必须保持不变(即“.”和“#”)。
保证存在解。如果有多个解决方案,您可以输出其中任何一个。
示例
输入 #1
3 4 2 #..# ..#. #...
输出 #1
#.X# X.#. #...
输入 #2
5 4 5 #... #.#. .#.. ...# .#.#
输出 #2
#XXX #X#. X#.. ...# .#.#