콩 옮기기

행이 $H$개, 열이 $W$개인 격자가 있다. 이 격자는 원통 모양이어서 왼쪽 끝과 오른쪽 끝이 맞붙어 있다. 따라서 1열과 $W$열은 서로 이웃한다.

격자의 일부 칸에는 접시가 놓여 있다. 처음에는 접시마다 콩이 최대 한 개씩 올려져 있다. 게임 도중에는 접시에 콩이 몇 개든 담길 수 있다.

앨리스와 밥이 번갈아 한 수씩 두며, 앨리스가 먼저 시작한다. 각 차례에 플레이어는 콩을 하나 골라 현재 위치를 $(r, c)$라 하고, 다음 규칙에 따라 옮긴다.

• 콩은 접시가 있는 칸으로만 옮길 수 있다.
• 콩은 자기가 전에 있었던 칸으로 다시 옮길 수 없다. 콩은 모두 서로 구별된다.
• $(r, c)$에 있는 콩은 아래로 한 칸($r < H$일 때만, $(r+1, c)$로), 오른쪽으로 한 칸($c < W$이면 $(r, c+1)$로, $c = W$이면 $(r, 1)$로), 왼쪽으로 한 칸($c > 1$이면 $(r, c-1)$로, $c = 1$이면 $(r, W)$로) 옮길 수 있다.

자기 차례에 콩을 하나도 옮길 수 없는 플레이어가 진다. 두 플레이어가 최선을 다할 때 누가 이기는지 구하라.

첫 줄에 정수 $H$와 $W$($1 \le H, W \le 1000$)가 주어진다. 이어서 길이 $W$인 문자열 $H$줄이 주어진다. $i$행 $j$열의 문자가 #이면 그 칸에 접시가 없고, .이면 콩이 없는 접시가 있고, B이면 콩이 한 개 있는 접시가 있다.

격자에 세 종류의 문자가 모두 들어 있다고 보장하지 않는다. 예를 들어 콩이 하나도 없는 격자도 유효한 입력이다.

두 플레이어가 최선을 다할 때 앨리스가 이기면 Alice를, 그렇지 않으면 Bob을 출력한다.

첫 번째 예시에서 콩은 처음에 $(1, 1)$에 있다. 앨리스가 콩을 $(1, 2)$로 옮긴다. 밥이 할 수 있는 수는 $(2, 2)$로 옮기는 것 하나뿐이다. 이어서 앨리스가 콩을 $(2, 3)$으로 옮기면 밥은 더 옮길 콩이 없으므로 앨리스가 이긴다.