Board Game

Alice and Bob play the following game. There is an $m \times n$ chessboard with some fields removed. Two pieces stand on two distinct, non-removed fields. Alice moves first, and then she and Bob alternate turns. On a turn a player moves one of the two pieces by one field horizontally or vertically. Either player may move either piece, regardless of which piece was moved on the previous turn. A piece may not be moved onto a removed field. If a player moves a piece onto the field occupied by the other piece, that piece is captured and the player wins.

After a while the game became boring: nobody could win and the pieces just chased each other. So they added a new rule: no player may move a piece so that a position that already occurred earlier in the game is repeated. A position is determined only by the set of fields occupied by the pieces (the two pieces are indistinguishable) and does not depend on whose turn it is. In addition, a player who cannot make a legal move loses. The game is now always finite and exactly one player wins. Determine who wins under optimal play.

The input consists of several instances, separated by single blank lines.

The first line of each instance contains two integers $m$ and $n$ ($1 \le m, n \le 8$). Each of the following $m$ lines contains $n$ characters describing the initial state of the board. Each character is one of:

• . for an empty field
• # for a removed field
• P for a field where one of the pieces starts

Each instance contains exactly two P characters.

For each instance, output a single line containing Alice wins. if Alice has a winning strategy, or Bob wins. otherwise.