AT_arc219_e [ARC219E] Equal Distribution

There is a shortcake in the shape of a $ 2H \times 2W $ grid. The cell at the $ i $ -th row from the top and the $ j $ -th column from the left is denoted as cell $ (i,j) $ . Cell $ (i,j) $ has one strawberry on it if $ S_{i,j}= $ `o`, and nothing if $ S_{i,j}= $ `x`. It is guaranteed that exactly $ 2HW $ cells have strawberries. Divide each cell of this shortcake into regions A and B so that all of the following conditions are satisfied: - Every cell belongs to exactly one of regions A and B. - Both regions A and B are connected. That is, for any two cells in the same region, one can move between them by repeatedly moving to an adjacent cell (sharing an edge) in the same region. - Both regions A and B contain exactly $ 2HW $ cells each. - Both regions A and B contain exactly $ HW $ strawberries each. It can be proved that such a partition always exists. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ H $ $ W $ $ S_{1,1} S_{1,2} \ldots S_{1,2W} $ $ S_{2,1} S_{2,2} \ldots S_{2,2W} $ $ \vdots $ $ S_{2H,1} S_{2H,2} \ldots S_{2H,2W} $

Output your solutions for the test cases in order, separated by newlines. For each test case, output your solution in the following format: > $ X_{1,1} X_{1,2} \ldots X_{1,2W} $ $ X_{2,1} X_{2,2} \ldots X_{2,2W} $ $ \vdots $ $ X_{2H,1} X_{2H,2} \ldots X_{2H,2W} $ Here, $ X_{i,j} $ is `A` if cell $ (i,j) $ belongs to region A, and `B` if it belongs to region B. If multiple valid partitions exist, any of them will be accepted.

### Sample Explanation 1 Consider the first test case. In the sample output, both regions A and B are connected and contain two cells each. Also, region A contains the strawberry at cell $ (1,1) $ , and region B contains the strawberry at cell $ (2,2) $ . Additionally, for example, the following output is accepted: ``` AB AB ``` ### Constraints - $ 1\le T $ - $ 1\le H\le W $ - $ H\times W\le 10^6 $ - $ S_{i,j} $ is `o` or `x`. - There are exactly $ 2HW $ pairs $ (i,j) $ with $ S_{i,j}= $ `o`. - The sum of $ H\times W $ over all test cases is at most $ 10^6 $ . - $ T, H, W $ are integers.