再过几天就是诺鲁孜节了（波斯人的新年），爷爷邀请他的全家人到他的花园来聚会。在众多的宾客中有 $k$ 个小孩。为了让这些孩子们在聚会中更开心，爷爷打算让他们玩一个捉迷藏的游戏。

整个花园可以看成一个有 $m\times n$ 个方格的网格。其中有一些（或许没有）方格被岩石堵住了，而剩下的方格就称为空格。如果两个格子共享同一条边，我们就称这两个格子是邻居。因此，每一个方格最多有4个邻居：两个水平方向的和两个垂直方向的。爷爷想把花园变成一个迷宫。为达此目的，他会在花园中的一些空格上种植灌木来堵住它们。而这些被灌木丛堵住的方格就不再是空格了。

一个迷宫必须具有下面所述的性质。在迷宫中的任意一对空格 $a$ 和 $b$ 之间都只会恰有唯一的一条简单路径相连。而这条由 $a$ 到 $b$ 的简单路径就是一个从空格 $a$ 开始并以空格 $b$ 结束的空格序列，序列中所有的方格必须是不同的，而且每两个相连的方格都是邻居。

一个小孩能够躲藏的方格当且仅当这个方格是空格，而且它恰有唯一一个邻居是空格。同一个空格内只能躲藏一个小孩。

题目会给出整个花园的地图作为输入文件。你的任务就是帮助爷爷构造一个能够躲藏尽量多小孩的迷宫。

实现细节

这是一个提交答案类型的题目，而且它有部份分。题目会给出 $10$ 个描述爷爷花园的输入文件。对于每个输入文件你应该提交一个含有迷宫的地图作作为输出文件。我们会根据你提交的每个输出文件中的迷宫能够躲藏的小孩数目来给出你的分数。

这道题目你不需要提交任何源代码。

输入格式

每个输入文件都描述了一个表示整个花园的网格，我们也会给出爷爷邀请的小孩数目 $k$。格式如下：

• 第 $1$ 行：$m\ n\ k$
• 第 $1+i$($1\le i\le m$)行：网格中的第 $i$ 行，它是一个长度为 $n$ 的字符串，包含以下的字符(中间没有空格):
  • '.'：一个空格，
  • '#'：一块岩石。

输出格式

• 第 $i$（$1\le i\le m$）行：迷宫中的第 $i$ 行（种植了灌木的花园）。它是一个长度为 $n$ 的字符串，包含以下字母（中间没有空格）：
  • '.'：一个空格，
  • '#'：一块岩石，
  • 'X'：一个灌木。（注意字母 X 必须为大写字母）

数据范围

• $1\le m,n\le 1024$

评分

一个有效的输出文件必须符合下列所有的条件：

• 除了把输入文件中的任意多个字母 '.' 修改成字母 'X'（即被灌木堵塞）外，输出的地图必须和输入的地图完全一样。
• 输出的地图必须符合在上文中提及的迷宫的所有性质。

对于某一个测试数据，如果你的输出不是有效的，你的这个测试数据的得分将会是 $0$。反之 ，你的得分是 $\min(10,10\cdot l/k)$，向下取值至小数后二位，这里的 $l$ 是指你输出的迷宫中能够最多藏着的小孩的数目，而 $k$ 则表示在在输入文件中题目要求你躲藏的小孩数目。对于一个测试数据，你能够得到 $10$ 分，当且仅当你的输出是一个能够躲藏 $k$ 个或更多小孩的迷宫。

对于每组测试数据都存在一个能得到 $10$ 分的答案。

请注意如果你的答案是有效的，但根据上述公式你的得分仍然是 $0$ 分，则在评分系统中，显示的结果将会是“Wrong Answer”。

例子

考虑以下输入：

4 5 5
....#
.#..#
...#.
....#

以下是其中一个有效的输出：

.X.X#
.#..#
...#X
XX..#

因为 $l=4$ 个小孩能够藏在这个迷宫中，所以这个解答能够得到 $10\cdot 4/5=8$ 分。小孩能够躲藏的方格如下以 O 所示。

OXOX#
.#.O#
...#X
XX.O#

以下的三个输出都不是有效的输出：

.XXX#                                ...X#                                XXXX#
.#XX#                                .#.X#                                X#XX#
...#.                                ...#X                                ..X#X
XX..#                                XXXX#                                ..XX#

在最左边的输出中，左上角的空格和最右列（位于右下方）的空格之间并没有一条简单路径。

在其他的两个输出中，对于任意两个空格之间都恰有两条简单路径相连。

下载

输入文件下载