K. Radio towers
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The military base has several buildings in the field with no any connections between them. To fix this situation the army decides to build some radio towers to transfer signals from any building to all others buildings. But the budget is very limited, so the cost of all towers must be minimal possible.

The field can be represented as the table $$$n \times m$$$. Each cell is either empty or contains the building. A radio tower must be build on top of every building, but also it is possible to put addition towers anywhere in the field. Each tower has a power, that can be specified by integer number from $$$1$$$ to $$$9$$$. That number determines the max covering distance of the tower (the distance is Euclidean). The cost of putting each tower in the cell is equal to $$$a$$$ plus $$$p^2$$$ where $$$p$$$ is a power of the tower and $$$a$$$ is a some constant.

Determine the places and parameters of radio towers to make possible to pass signals from any building to any other building (maybe through some proxies) with minimal summary cost.

Input

The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 12$$$, $$$2 \leq n \times m \leq 28$$$).

Next $$$n$$$ lines contain $$$m$$$ symbols each. They describe the field the following way: "." is an empty cell, "*" is a cell with building. The field contains at least $$$2$$$ buildings.

The last line contains one integer number $$$a$$$ ($$$1 \leq a \leq 100$$$).

Output

Output $$$n$$$ lines of $$$m$$$ symbols: the field with placed towers, where "." is an empty cell, "x" is a cell with a tower having power $$$x$$$ where $$$x$$$ is an integer number from $$$1$$$ to $$$9$$$.

Examples
Input
3 3
..*
...
*..
4
Output
2.2
...
2..
Input
5 5
*....
....*
.....
*....
....*
9
Output
1....
2...2
.....
2.2.2
....1
Input
4 7
......*
.......
.......
*......
100
Output
......7
.......
.......
7......