나이트

$n$행 $m$열의 체스판이 있다. 체스판의 일부 칸은 깨져 있다. 체스판에는 앨리스와 밥이 각각 조종하는 나이트가 하나씩 있다. 나이트의 이동은 두 매개변수 $r$과 $c$로 정해진다. 한 번의 이동에서 앨리스 또는 밥은 자기 나이트를 가로로 $r$칸, 세로로 $c$칸 떨어진 칸이나, 세로로 $r$칸, 가로로 $c$칸 떨어진 칸으로 옮길 수 있다.

앨리스와 밥은 번갈아 가며 두고, 앨리스부터 시작한다. 각 차례에 플레이어는 자기 나이트를 움직인다. 깨진 칸이나 상대 나이트가 있는 칸으로는 나이트를 옮길 수 없다.

추가 조건이 있다. 나이트의 배치는 순서쌍 $(a, b)$로 나타내며, $a$는 앨리스의 칸, $b$는 밥의 칸이다. 이전에 나온 배치는 다시 만들 수 없다.

차례에 움직일 수 없는 플레이어는 진다. 두 플레이어가 최선을 다할 때 승자를 구하라.

첫째 줄에 정수 $n$, $m$, $r$, $c$가 주어진다 ($1 \leq n, m \leq 1000$, $0 \leq r < n$, $0 \leq c < m$).

이어지는 $n$개의 줄에는 길이 $m$의 문자열이 주어지며 체스판을 나타낸다. 각 칸은 다음 네 가지 중 하나이다.

• @: 깨진 칸이다.
• .: 깨지지 않은 칸이다.
• A: 깨지지 않은 칸이며 앨리스 나이트의 시작 위치이다.
• B: 깨지지 않은 칸이며 밥 나이트의 시작 위치이다.

A와 B는 각각 체스판에 정확히 한 번씩 나타난다.

승자의 이름을 출력한다. Alice 또는 Bob이다.

첫 번째 이동에서 앨리스가 나이트를 $(2, 3)$ 칸으로 옮긴다.

두 번째 이동에서 밥이 나이트를 $(1, 3)$ 칸으로 옮긴다.

세 번째 이동에서 앨리스가 나이트를 다시 $(1, 1)$ 칸으로 옮긴다.

네 번째 이동에서 밥은 나이트를 $(2, 1)$ 칸으로 되돌릴 수 없다. 그러면 $(1, 1), (2, 1)$ 배치가 시작 배치와 같아져 이미 나온 배치가 반복되기 때문이다. 앨리스가 이긴다.