Battlefield Simulation

Two cities, \(A\) and \(B\), fight a fierce battle on a battlefield represented by an \(n\) by \(m\) grid. Each cell of the grid is one of the following characters:

• #: An empty cell.
• A: A soldier from city \(A\).
• B: A soldier from city \(B\).
• H: A wall.

Rows are numbered from \(1\) to \(n\) (top-down) and columns from \(1\) to \(m\) (left-right). City \(A\) is on the left and city \(B\) on the right. Hence, for each row, all \(A\) soldiers appear to the left of any \(B\) soldiers. Furthermore, if a wall exists in a row, it is placed between the \(A\) and \(B\) soldiers (and there is at most one wall per row).

The battle unfolds row by row in two phases:

1. Retreat / Charge phase:
   • If the row contains a wall (character H):
     • Count \(c_A\): the number of \(A\) soldiers to the left of the wall.
     • Count \(c_B\): the number of \(B\) soldiers to the right of the wall.
     • The \(A\) soldiers retreat toward their own boundary (the left border) and are rearranged contiguously starting at column \(1\). The wall remains in its original column. The positions between the \(A\) block and the wall are filled with #. Similarly, the \(B\) soldiers retreat toward the right boundary and are rearranged contiguously at the right end. The cells between the wall and the \(B\) block are filled with #.
     • Formally, if the wall is at column \(i_w\) (1-indexed), then the new row is constructed as follows: \( \underbrace{A\,A\,\ldots\,A}_{c_A}\,\underbrace{#\,#\,\ldots\,#}_{i_w - 1 - c_A}\,H\,\underbrace{#\,#\,\ldots\,#}_{m - i_w - c_B}\,\underbrace{B\,B\,\ldots\,B}_{c_B} \)
   • If the row does not contain a wall:
     • Let \(c_A\) be the total number of \(A\) soldiers and \(c_B\) the total number of \(B\) soldiers.
     • If \(c_A = c_B\), all soldiers fall and the row becomes all #.
     • If \(c_A > c_B\), the \(A\) soldiers win. They charge toward enemy city \(B\) (i.e. toward the right boundary) and occupy the rightmost \(c_A\) cells, with the remaining cells filled with #. Formally, the new row is: \( \underbrace{#\,\ldots\,#}_{m - c_A}\,\underbrace{A\,\ldots\,A}_{c_A} \)
     • If \(c_B > c_A\), the \(B\) soldiers win. They charge toward enemy city \(A\) (i.e. toward the left boundary) and occupy the leftmost \(c_B\) cells, with the remaining cells filled with #. Formally, the new row is: \( \underbrace{B\,\ldots\,B}_{c_B}\,\underbrace{#\,\ldots\,#}_{m - c_B} \)
2. Vertical Elimination: After the above phase for all rows, every soldier (either \(A\) or \(B\)) is examined simultaneously. If a soldier has a friendly soldier (same letter) immediately above or below, that soldier is removed (the cell becomes #). Note that this check is only vertical (adjacent rows) and is applied based on the grid after the retreat/charge phase.

Your task is to simulate this battle and output the final configuration of the grid.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns). Following this, there are \(n\) lines, each containing a string of length \(m\) which represents a row of the battlefield.

outputFormat

Output the final configuration of the battlefield as \(n\) lines after all simulation steps.

sample

1 8
#A##B#B#

BB######