How to Move the Beans

A grid has $H$ rows and $W$ columns. The grid is cylindrical: its left and right sides are glued together, so columns $1$ and $W$ are neighbors.

Some grid squares contain dishes. Initially, beans are placed on some of these dishes, with at most one bean per dish. Later in the game, a dish may hold any number of beans.

Alice and Bob take turns, and Alice moves first. On each turn, a player picks any bean, denotes its current row and column by $(r, c)$, and moves it by these rules:

• A bean can be moved only to a square with a dish.
• A bean cannot be moved to a square where this same bean was before. All beans are distinguishable.
• From $(r, c)$, a bean can move one square down (to $(r+1, c)$, only when $r < H$), one square to the right (to $(r, c+1)$ if $c < W$, or to $(r, 1)$ if $c = W$), or one square to the left (to $(r, c-1)$ if $c > 1$, or to $(r, W)$ if $c = 1$).

A player who cannot move any bean on their turn loses. Determine who wins if both players play optimally.

The first line contains two integers $H$ and $W$ ($1 \le H, W \le 1000$). Then $H$ lines follow, each a string of length $W$. The $j$-th character of the $i$-th line is # if there is no dish at $(i, j)$, . if there is an empty dish, and B if there is a dish with exactly one bean.

The grid is not guaranteed to contain all three characters. For example, a grid with no beans is valid.

Print Alice if Alice wins when both players play optimally. Otherwise, print Bob.

In the first example, the only bean starts at $(1, 1)$. Alice moves it to $(1, 2)$. Bob's only move is to $(2, 2)$. Alice then moves the bean to $(2, 3)$, and Bob has no moves left, so Alice wins.