暂无测试数据。

请在Qingyu's Online Judge System修复后在OJ上提交

VIJOS不资瓷这类题目 QAQ

警告：数据加强！

Background

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

Description

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

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

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

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

Implementation details

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

除了把输入文件中的任意多个字母.修改成字母X（即被灌木堵塞）外，输出的地图必须和输入地图完全一样。

输出的地图必须符合在上文中提及的迷宫的所有性质。

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

Format

Input

原题目为提交答案题，这里修改为评测题。
你需要从标准输入中读入整个输入文件。

题目会给出 \(10\) 个描述爷爷花园的输入文件。对于每个输入文件你应该输出一个答案。我们会根据你提交的每个输入文件中的迷宫能够躲藏的小孩数目来给出你的分数。

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

第 \(1\) 行： 1 : \(m, n, k\)

第 \(1 + i\) 行： 网格中的第 \(i\) 行，它是一个长度为 \(n\) 的字符串，包含以下的字符（中间没有空格）：

.： 一个空格，

#： 一块岩石。

Output

第\(i\) 行： 迷宫中的第 \(i\) 行（种植了树木的花园）。它是一个长度为 \(n\) 的字符串，包含以下字母（中间没有空格）：

• . ： 一个空格，

• #： 一块岩石，

• X： 一个灌木（注意字母X必须为大写字母）。

Sample 1

Input

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

Output

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

Limitation

基础数据: 50%

对于下面的数据，分配2.0s的时间和128MB的空间

对于30%的数据，\(n, m \leqslant 64\)。
对于50%的数据，\(n, m \leqslant 256\)

对于下面的数据，分配5.0s的时间和256MB的空间

对于70%的数据，\(\min(m, n) \leqslant 128, \max(m,n) \leqslant 1024\)

对于下面的数据，分配20.0s的时间和256MB的空间

对于100%的数据，\(n, m\leqslant 1024\)

加强数据: 50%

对于这组数据，你可能需要优化常数。如果因为常数原因被卡掉，可在代码头部加入：

#pragma GCC optimize("Ofast")


对于下面的数据，分配0.5s的时间和8MB的空间

对于30%的数据：\(n, m \leqslant 64\)
对于50%的数据，\(n, m \leqslant 128\)
对于70%的数据，\(n, m \leqslant 256\)

对于下面的数据，分配0.75s的时间和16MB的空间

另有30%的数据，\(\min(m, n) \leqslant 128, \max(m,n) \leqslant 1024\)

Hint

样例输出是其中一个有效的输出。

对于这个输出，因为 l=4 个小孩能够这个迷宫中，所以这个解答能够得到8 分。