Problem Description

There is a grid with $ H $ rows and $ W $ columns. Each cell of the grid can either have a plate or not.

Among the cells with plates, some cells have beans on them. Each bean is distinguishable, and multiple beans can be placed on a single plate.

Alice and Bob are planning to play the following game using this grid:

• Alice starts first, and they take turns alternately.
• On their turn, a player moves one bean according to the "rules for moving beans on a turn" described later. If there are no beans that can be moved, the player immediately loses, and the other player wins.

Determine which player wins when both play optimally.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ c_{1,1} $ $\cdots$ $ c_{1,W} $ $\vdots$ $ c_{H,1} $ $\cdots$ $ c_{H,W} $

Here, $ c_{i,j} $ represents the state of the cell $ (i,j) $ in the grid as follows:

• When $ c_{i,j}= $#, the cell $ (i,j) $ does not have a plate.
• When $ c_{i,j}= $., the cell $ (i,j) $ has a plate without beans.
• When $ c_{i,j}= $B, the cell $ (i,j) $ has a plate with one bean.

Output Format

Output Alice if Alice wins, and Bob if Bob wins.

Sample Input and Output

Sample Input #1

2 3
B.#
#..

Sample Output #1

Alice

Sample Input #2

1 1
B

Sample Output #2

Bob

Sample Input #3

1 3
B#.

Sample Output #3

Alice

Sample Input #4

5 18
#.#..#.#..###..###
##...#.#..#.#..#..
#....#.#..###..#..
##...#.#..#....#..
#.#..###..#....###

Sample Output #4

Bob

Notes/Hints

Rules for Moving Beans on a Turn

Let $ (i,j) $ denote the coordinates of the $ i $-th row and $ j $-th column. $(1 \leq i \leq H, 1 \leq j \leq W)$

First, choose one bean. If the current position of this bean is $ (i,j) $, move it once according to one of the following three types of moves that satisfy all the conditions:

• Three types of moves:
• When $i+1 \leq H$, move to $ (i+1,j) $.
• When $ j=1 $, move to $ (i,W) $. Otherwise, move to $ (i,j-1) $.
• When $ j=W $, move to $ (i,1) $. Otherwise, move to $ (i,j+1) $.
• Conditions:
• The destination cell has a plate.
• The chosen bean has never visited the destination cell before.

Constraints

• $1 \leq H,W \leq 1000$
• $ H,W $ are integers.

Sample Explanation 1

Initially, the bean is at $ (1,1) $.
- On Alice's first turn, she can only move the bean to $ (1,2) $.
- On Bob's first turn, he can only move the bean to $ (2,2) $.
- On Alice's second turn, she can only move the bean to $ (2,3) $.
- On Bob's second turn, he cannot move the bean.
Thus, Bob loses, and Alice wins.

Sample Explanation 3

Note that the bean can be moved from $ (1,1) $ to $ (1,3) $.

Sample Explanation 4

There may be no beans present.

见题面 Input 部分

见题面 Output 部分