/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
2H 行 2W 列のグリッド状のショートケーキがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。マス (i,j) には S_{i,j}= o ならばイチゴが 1 つ乗っており、 S_{i,j}= x ならば何もありません。ここで、イチゴが乗ったマスはちょうど 2HW マスであることが保証されます。
このショートケーキの各マスを以下の条件を全て満たすように領域 A, B に分けてください。
- 全てのマスは領域 A, B のちょうど一方に含まれる。
- 領域 A, B はどちらも連結である。つまり、任意の同じ領域内の 2 マスは上下左右に辺で接している同じ領域内のマスに移動する操作を繰り返すことで互いに移動可能である。
- 領域 A, B はどちらもマスを 2HW マスずつ含む。
- 領域 A, B はどちらもイチゴを HW 個ずつ含む。
ただし、そのような分け方が必ず存在することが証明できます。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T
- 1\le H\le W
- H\times W\le 10^6
- S_{i,j} は
oまたはx - S_{i,j}=
oを満たす (i,j) がちょうど 2HW 個存在する - 全てのテストケースにおける H\times W の総和は 10^6 以下
- T,H,W は整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
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}
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、答えを以下の形式で出力せよ。
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}
ここで、X_{i,j} はマス (i,j) が領域 A に含まれる場合は A、領域 B に含まれる場合は B とする。
条件を満たす分け方が複数存在する場合、どれを出力しても正答となる。
入力例 1
3 1 1 ox xo 1 2 oxxx ooxo 2 3 oooxxx oooxxx xoxxxx xooooo
出力例 1
AA BB AAAB ABBB AAABBB AAAAAB ABABAB ABBBBB
1 番目のテストケースについて考えます。
出力例の領域 A, B はどちらも連結で 2 つのマスを含んでいます。また、領域 A はマス (1,1) のイチゴを、領域 B はマス (2,2) のイチゴを含んでいます。
他にも、例えば以下のような出力でも正答となります。
AB AB
Score : 600 points
Problem Statement
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.
Constraints
- 1\le T
- 1\le H\le W
- H\times W\le 10^6
- S_{i,j} is
oorx. - 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.
Input
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
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 Input 1
3 1 1 ox xo 1 2 oxxx ooxo 2 3 oooxxx oooxxx xoxxxx xooooo
Sample Output 1
AA BB AAAB ABBB AAABBB AAAAAB ABABAB ABBBBB
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