AT_arc219_e [ARC219E] Equal Distribution

$ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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` とする。 条件を満たす分け方が複数存在する場合、どれを出力しても正答となる。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 出力例の領域 A, B はどちらも連結で $ 2 $ つのマスを含んでいます。また、領域 A はマス $ (1,1) $ のイチゴを、領域 B はマス $ (2,2) $ のイチゴを含んでいます。 他にも、例えば以下のような出力でも正答となります。 ``` AB AB ``` ### Constraints - $ 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 $ は整数