H :: Trail

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Have you ever read any description of some encryption algorithm? These descriptions almost always include messages being sent between Alice and Bob. We (the people organizing the 2011 Central Europe Regional Contest) think that those descriptions are too impersonal — considering these two people are probably the most famous cryptographers in the whole world, we know so little about them. They deserve more attention, don’t you think? We can learn about their hobbies, for instance.

In their free time, Alice and Bob like to play a game inspired by Tron. In this game, you race a car through a square grid and you need to avoid hitting obstacles placed in the grid. Furthermore, the car leaves a permanent trail, which you also need to avoid. The car only moves in the four cardinal directions (east, west, north, or south). In their version of the game, Alice and Bob alternate in controling the car—Alice starts, moves the car from its initial position to one of the adjacent positions in the grid, then Bob takes over and moves the same car to another adjacent position, etc.

http://sharecode.ir/assets/problem_images/1146_41d524e9e817e09a7187698d9a3923cd.jpg

The player who crashes the car (i.e., moves it to a position occupied by an obstacle, or to one of the previously visited positions) loses. Both Alice and Bob are incredibly skilled players and never make mistakes; in particular, they only crash if there is no possible move from their current position that would avoid it. Given the map of the obstacles, your task is to determine which player wins from which initial position.

Input

The input contains descriptions of several game fields. The first line of each description contains two integers N and E (1 ≤ N, E ≤ 100) — the size of the grid in the north-south and in the east-west directions. The following N lines describe the map. Each of the lines contains a string of E characters, where the j-th character on the i-th line determines the state of the position with coordinates (j, i). The possible characters are “.” (a dot) if the position is empty and the uppercase letter “X” if there is an obstacle. All positions not covered by the map (i.e., with coordinates (j, i) such that i ≤ 0 or j ≤ 0 or i > N or j > E) are forbidden and not used in the game, they work as if there were obstacles.
The last game field is followed by a line containing two zeros.

Output

For each game field, output N lines of strings of length E, showing whether Alice or Bob wins when the game starts from the given location. The j-th character on the i-th line should be “A” if Alice wins when starting from the position (j, i), “B” if Bob wins, or “X” if the position contains an obstacle.
After each output, print one empty line.

Sample Input

1 1
.
3 3
...
.X.
...
1 4
....
3 3
X.X
...
X.X
5 8
........
.XX.XXX.
.X..X...
.X.XX.X.
........
0 0

Sample Output

B

AAA
AXA
AAA

AAAA

XBX
BAB
XBX

BABABABA
AXXBXXXB
BXBAXABA
AXAXXBXB
BABABABA
Submit

Source: Central Europe Regional Contest 2011