AT_kupc2020_h Beans on the Grid

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_h $ H $ 行 $ W $ 列のグリッドがあります。グリッドの各マスには、皿が置かれているマスと皿が置かれていないマスがあります。 皿が置かれているマスのうち、いくつかのマスに豆が置いてあります。それぞれの豆は区別でき、$ 1 $ つの皿には複数の豆を乗せることができます。 このグリッドを使って、AliceとBobは次のようなゲームをしようと考えています。 - Aliceを先手として、手番を交互に繰り返す。 - 自分の手番では、後述する「手番における豆の動かし方」に沿って豆を1つ動かす。動かせる豆が存在しない場合、即座に手番のプレイヤーは敗北し、手番でないプレイヤーは勝利する。 両者が最適に行動したとき、どちらが勝利するか答えてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ c_{1,1} $ $ \cdots $ $ c_{1,W} $ $ \vdots $ $ c_{H,1} $ $ \cdots $ $ c_{H,W} $ ただし、 $ c_{i,j} $ はグリッドのマス $ (i,j) $ の状態を以下の形式で表している。 - $ c_{i,j}= $`#` のとき、マス $ (i,j) $ には皿がない。 - $ c_{i,j}= $`.` のとき、マス $ (i,j) $ には豆が入っていない皿がある。 - $ c_{i,j}= $`B` のとき、マス $ (i,j) $ には豆が1つ入っている皿がある。

Aliceが勝利するときは`Alice`と、Bobが勝利するときは`Bob`と出力せよ。

### 手番における豆の動かし方 以下、$ i $ 行 $ j $ 列目の座標を $ (i,j) $ と表記する。$ (1\ \leq\ i\ \leq\ H,\ 1\ \leq\ j\ \leq\ W) $ まず豆を $ 1 $ つ選ぶ。この豆の現在位置を $ (i,j) $ とすると、以下の $ 3 $ 種類の動きで条件をすべて満たすもののうち、$ 1 $ 種類を $ 1 $ 度だけ行う。 - $ 3 $ 種類の動き - $ i+1\ \leq\ H $ のとき、$ (i+1,j) $ に移動させる。 - $ j=1 $ のとき、$ (i,W) $ に移動させる。そうでないとき、$ (i,j-1) $ に移動させる。 - $ j=W $ のとき、$ (i,1) $ に移動させる。そうでないとき、$ (i,j+1) $ に移動させる。 - 条件 - 移動先のマスに皿がある。 - 選んだ豆が初めて移動先のマスに訪れる。 ### 制約 - $ 1\ \leq\ H,W\ \leq\ 1000 $ - $ H,W $ は整数である。 ### Sample Explanation 1 はじめ、豆は $ (1,1) $ にあります。 - Aliceの $ 1 $ 回目の手番では、豆を $ (1,2) $ に移動させるしかありません。 - Bobの $ 1 $ 回目の手番では、豆を $ (2,2) $ に移動させるしかありません。 - Aliceの $ 2 $ 回目の手番では、豆を $ (2,3) $ に移動させるしかありません。 - Bobの $ 2 $ 回目の手番では、豆を動かすことができません。 したがって、Bobの敗北となり、Aliceの勝利となります。 ### Sample Explanation 3 豆を $ (1,1) $ から $ (1,3) $ へ動かせることに注意してください。 ### Sample Explanation 4 豆が存在しないこともあります。