Racing Car Trail

Alice and Bob enjoy a racing game inspired by Tron. A single car speeds across a square grid and must avoid the obstacles placed on it. The car also leaves a permanent trail on every cell it passes through, and that trail must be avoided as well. The car moves only in the four cardinal directions (north, south, east, or west), one cell at a time.

The two players take turns steering the same car. Alice always moves first: she slides the car from its current cell to an adjacent cell. Then Bob moves it to another adjacent cell, then Alice again, and so on.

Once a cell has been visited it is blocked by the trail and can never be entered again. On your turn you must move the car to an adjacent cell that is empty and has not been visited. A player who has no such move is forced to crash the car and immediately loses. Both players are flawless and never make an avoidable mistake: a player loses only when every move from the current cell would hit an obstacle, leave the grid, or step onto the trail.

For a fixed obstacle map, decide for every possible starting cell which player wins the game that begins with the car parked on that cell.

The input describes several independent boards.

Each board starts with a line containing two integers N and E (1 ≤ N, E ≤ 100): the number of rows in the north-south direction and the number of columns in the east-west direction.

The next N lines describe the grid. Each line is a string of exactly E characters; the j-th character of the i-th line is the cell with coordinates (j, i) (column j, row i, both 1-based). The character is . for an empty cell and the uppercase letter X for a cell that holds an obstacle.

Every position outside the grid — any (j, i) with i ≤ 0, j ≤ 0, i > N, or j > E — is forbidden and behaves exactly like an obstacle.

The list of boards ends with a line containing two zeros. That terminating line must not be processed.

For each board, print N lines, each a string of length E.

The j-th character of the i-th line describes the cell (j, i):

• A if Alice (the first player) wins when the car starts on that cell;
• B if Bob (the second player) wins when the car starts on that cell;
• X if that cell holds an obstacle.

Separate the outputs of consecutive boards with a single blank line.