보드 게임

앨리스와 밥이 다음 게임을 한다. $m \times n$ 크기의 체스판이 있고, 일부 칸은 제거되어 있다. 제거되지 않은 서로 다른 두 칸에 말이 하나씩, 모두 두 개가 놓여 있다. 앨리스가 먼저 두고, 이후 밥과 번갈아 둔다. 한 번의 차례에는 두 말 중 하나를 상하좌우로 인접한 칸으로 한 칸 옮긴다. 두 사람 모두 어느 말이든 옮길 수 있으며, 직전에 어떤 말을 옮겼는지는 상관없다. 말은 제거된 칸으로는 옮길 수 없다. 어떤 말을 다른 말이 있는 칸으로 옮겨 잡으면 그 사람이 이긴다.

한동안 두다 보니 게임이 지루해졌다. 아무도 이기지 못하고 두 말이 서로 쫓기만 했기 때문이다. 그래서 새로운 규칙을 추가했다. 게임 도중 이미 나왔던 배치가 다시 나오도록 말을 옮길 수는 없다. 배치는 두 말이 놓인 칸들의 집합만으로 정하며(두 말은 서로 구별하지 않는다), 그 배치에서 누구 차례인지는 따지지 않는다. 또한 합법적인 수를 둘 수 없는 사람은 진다. 이제 게임은 항상 유한하며 반드시 한 사람이 이긴다. 두 사람이 최선을 다해 둘 때 누가 이기는지 구하여라.

입력은 여러 개의 인스턴스로 이루어지며, 인스턴스 사이는 빈 줄 하나로 구분된다.

각 인스턴스의 첫 줄에는 두 정수 $m$과 $n$이 주어진다 ($1 \le m, n \le 8$). 이어지는 $m$개의 줄에는 각각 $n$개의 문자가 주어져 판의 초기 상태를 나타낸다. 각 문자는 다음 중 하나이다.

• . : 빈 칸
• # : 제거된 칸
• P : 말이 놓인 칸

각 인스턴스에는 정확히 두 개의 P가 있다.

각 인스턴스에 대해, 앨리스에게 승리 전략이 있으면 Alice wins.를, 없으면 Bob wins.를 한 줄에 출력한다.