Hide and Seek Maze

Grandpa is celebrating Nowruz (the Persian New Year) by inviting the whole family to his garden for a gathering. Among the guests there are k children. To make the party more fun for them, Grandpa wants to let the children play a game of hide-and-seek in a maze he creates in his garden.

The garden is represented by an m×n grid. Some cells may be blocked by rocks, and the remaining cells (depicted by a dot, i.e. .) are considered empty. Two cells sharing a common side are called neighbors (so each cell has at most 4 neighbors, two in the horizontal direction and two in the vertical direction).

Grandpa can plant bushes on any number of empty cells (i.e. change some . into X) in order to block them. Once a cell is blocked by bushes it is no longer considered empty.

A maze must satisfy the following property: For any two empty cells \(a\) and \(b\) in the maze there exists exactly one simple path connecting them. Here a simple path from \(a\) to \(b\) is defined as a sequence of distinct empty cells starting with \(a\) and ending with \(b\), where every two consecutive cells are neighbors.

A child can hide in an empty cell if and only if that cell has exactly one empty neighbor in the maze. Moreover, each empty cell can hide at most one child.

You are given the garden map as input. Your task is to output a modified map that becomes a valid maze and in which the number of hiding spots (leaves in the maze tree) is as high as possible – ideally at least k hiding spots.

Scoring: An output is considered valid if it meets all of the following conditions:

• The only changes to the input are that any number of the . characters may have been replaced by X (indicating bushes/planted obstacles). All other characters must remain unchanged.
• The output maze satisfies the maze property mentioned above, i.e. for any two empty cells \(a\) and \(b\) there is exactly one simple path between them.

For each test case, if your output is valid, your score is computed as \(\min\Big(10,\,10\cdot\frac{l}{k}\Big)\) (rounded down to two decimal places), where \(l\) is the maximum number of children that can hide in the maze. A full score (10 points) is awarded if and only if \(l \ge k\). Note: Even if your output is valid, if the score according to the above formula is 0, the result will be judged as "Wrong Answer".

It is guaranteed that for each test case there exists an output that can achieve full score.

inputFormat

The first line contains three integers m, n and k (1 ≤ m,n ≤ 1000, k ≥ 1), where m and n specify the dimensions of the garden, and k is the number of children to hide. The following m lines each contain n characters. In the garden map, a dot . represents an empty cell that can either remain empty or be blocked (by changing it to X), and any other character (for example, #) represents an obstacle (such as a rock) which must remain unchanged.

outputFormat

Output the modified garden map consisting of m lines with n characters per line. You are allowed to change some of the . characters into X such that the resulting maze is valid (i.e. the set of empty cells forms a tree with a unique simple path between any two empty cells) and maximizes the number of hiding spots. A cell is a hiding spot if it is empty and has exactly one empty neighbor.

sample

3 3 2
...
...
...

.XX
..X
X..