Alice is playing a game of Twos and Threes. Twos and Threes is a one-player game played on a two-dimensional board containing a region to be covered. Alice has an infinite collection of dominoes and triominoes, i.e. tiles of the following shapes:
Alice can place her tiles on the board in any location and orientation. She wins the game if she finds a tiling of the region on the board such that all squares in the region are covered, all squares not in the region are not covered, and no two tiles overlap. Your task is to help Alice find a winning tiling of the region, or determine that the game cannot be won.
The first line of input contains two integers and .
The next lines each contain characters which are either
., representing squares that are in the region and squares that are not in the region, respectively.
If it is impossible to win the game, output
Otherwise, output lines each consisting of characters which are either
. or any letter from
Z, representing a winning tiling of the region. Adjacent letters which are the same should represent squares that are covered by the same tile. You may use the same letter to represent different tiles, as long as those tiles do not cover orthogonally adjacent squares.
4 7 .#...## .####.# ..#...# ####.##
.A...CC .ABBB.C ..A...B CCAA.BB
Explanation for Sample
The sample output corresponds to the following tiling: