399. Berodoskar Development

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Not far away from Berland there is a small stony isle in the ocean. The name of the isle is Berodoskar and it is an ideal place for a military base. The only problem is lack of fresh water, but such a negligible problem will never stop Berl III, the King of Berland. He has stated that there would be exactly two water-storage reservoirs with desalinated water. The best way to organize reservoirs is to use existing craters located on the isle and connect them with the ocean by a water-pipe. And you are the person responsible for the water-storage system creation. You have a map of Berodoskar on which the isle is represented as a rectangle divided into unit squares by horizontal and vertical lines. Each unit square is marked with either '' character if it contains a part of crater or with '' character if there is no crater on this square. If two squares marked with '' have the common edge they are considered as parts of one crater. There are no squares marked with '' connected with the ocean. The whole area around the square is the ocean. The water-pipe you are to create should connect any two of craters with the ocean. It is allowed to connect more than two craters, but at least two craters should be connected. The water-pipe will consist of segments connected by edge and each segment will occupy the whole non-crater unit square. A pipe is connected with a crater if they have a common edge. You want to minimize number of squares involved into water-storage system creation. It is possible that two independent water-pipes are more efficient than one branched (see examples).
Input
The first line contains two integer numbers N and M — number of unit squares in vertical and horizontal directions (3≤ N, M≤ 15). After that N lines follow describing the isle. Each line contains exactly M characters '' or ''. It is guaranteed that there are at least two craters reachable from the ocean.
Output
Output N lines with M characters in each — an isle map is in the same format as in the input, but with the water-pipe indicated. Squares with the water-pipe should be marked with '' instead of ''. If there are several solutions with the same minimal number of squares used, output any one of them.
Example(s)
sample input
sample output
5 7
.......
.......
..X....
.....X.
.......
.......
.......
**X....
.....X*
.......

sample input
sample output
10 13
.............
.............
..XXXXX......
..X..X.......
..X.X.X.X....
..X...X......
..XXXXX......
.............
.............
.............
........*....
........*....
..XXXXX**....
..X..X..*....
..X.X.X.X....
..X...X......
..XXXXX......
.............
.............
.............

: in second example you are not allowed to connect a crater with the ocean via another crater.