CONTAMINATION - Contamination

no tags 

The year is 2241, and the colonization of other planets is now a reality. You work in the control center of resources on the planet URI-942, mainly controlling the water supplies. The water is stored in underground tanks, protected from the high surface temperatures.

But, your fellow colleagues Ana and Márcio found some shortcomings in the walls of tanks, which can lead to contamination of the water stock. Your colleagues were able to identify the points where there may be flaws with the infiltration of contaminants. Knowing that the contaminants spread throughout the water tank affected, your task is to estimate the contamination of the water according to the maps provided by your peers.

The maps were discretized into cells, and cells may correspond to a region of rock, water (tank) or a contaminant. Because of the cracks, a cell with contaminant contaminate adjacent cells (left, right, above and below) containing water, but contamination is barred by cells of rock.

Input

The input consists of several maps, and a description of each map starts with a line containing two integers N and M, corresponding to the number of rows and columns of the map. The following N lines describe the map, each line containing M characters, beyond the jump line. Possible characters are A, which is a cell containing water, X represents a cell with rock and T represents a cell with contaminant.

The entry ends when N = M = 0, the case should not be processed. In all maps, N and M are less than or equal to 50.

Output

For each map, print an estimation of future contamination. This estimation should match the original map (as given in the input), but replacing the cells with water that have been contaminated by the character T. Leave a blank line after each map (including the last map).

Example 1

Input:
6 7
XXAAXXX
XXAAXAX
XXXXAXX
XAAAAAX
TAAXAAA
XXXXXXX
3 3
TTT
XXX
AAA
0 0

Output:
XXAAXXX
XXAAXAX
XXXXTXX
XTTTTTX
TTTXTTT
XXXXXXX

TTT
XXX
AAA


hide comments
nadstratosfer: 2018-09-27 11:59:50

I never get bored of such problems. Nice story, too. Good DFS for beginners to warm up for eg. UCV2013H.


Added by:Coach UTN FRSF
Date:2015-09-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY