나이트 게임

시간 제한2초메모리 제한1024 MB

요약

H행 W열 체스판에서 나이트가 (x, y)에 있을 때, 두 사람이 번갈아 방문하지 않은 칸으로 나이트를 옮기는 게임의 승자를 판정합니다.

문제

이 게임의 규칙은 다음과 같다.

나이트와 $H$ 행 $W$ 열의 체스판이 있다. 위에서 $i$ 번째 행, 왼쪽에서 $j$ 번째 열에 있는 칸을 칸 $(i, j)$ 라고 한다. 처음에 나이트는 칸 $(x,y)$ 에 놓여 있다.
앨리스와 밥이 앨리스부터 번갈아 행동한다. 각 차례마다 나이트의 이동 규칙에 따라 아직 방문하지 않은 칸 중 하나로 나이트를 옮긴다.
나이트는 $(x\_1,y\_1)$ 에서 $(x\_2, y\_2)$ 로 이동할 수 있으며, 이는 $(x\_1 - x\_2)^2 + (y\_1 - y\_2)^2$ 이 $5$ 일 때만 가능하다.
나이트를 옮길 수 없는 사람이 패배한다.

두 사람이 최선을 다할 때 앨리스와 밥 중 누가 이기는지 판단한다. $T$ 개의 테스트 케이스에 대해 답한다.

방문하지 않은 칸은 다음과 같이 정의한다.

$T$

$\text{case}\_1$

$\vdots$

$\text{case}\_T$

$\text{case}\_i$ 는 $i$ 번째 테스트 케이스이다.

각 테스트 케이스는 다음 형식으로 주어진다.

$H$ $W$ $x$ $y$

$T$ 개의 줄에 출력한다. $i$ 번째 줄에는 $i$ 번째 테스트 케이스의 승자인 Alice 또는 Bob을 출력한다.