Baklawa
시간 제한2초메모리 제한512 MB
최대 100개의 독이 있는 단위 세포를 가진 거대한 직육면체에서, 두 사람이 번갈아 안전한 직육면체 조각을 잘라내며 두는 게임에서 최적 플레이 시 승자를 판정한다.
문제
Baklawa(또는 baklava)는 중동의 달콤한 디저트로, 주로 필로 반죽 시트, 호두, 설탕 시럽으로 만들어진다. 작은 정육면체 조각으로 잘려 여러 층을 담은 직육면체 상자에 담겨 나온다.
Alice와 Bob은 "마지막 Baklawa 게임"이라 부르는 게임을 즐긴다. 규칙은 다음과 같다.
- X × Y × Z개의 Baklawa 세포로 이루어진 직육면체를 골라 게임한다.
- N개의 독성 세포가 있으며, 두 플레이어 모두 그 위치를 안다.
- Alice가 먼저 두고, 두 플레이어가 번갈아 둔다.
- 자신의 차례에 플레이어는 직육면체를 두 직육면체로 잘라야 하며, 그중 적어도 하나는 안전해야 한다(독성 큐브를 포함하지 않아야 한다). 그리고 안전한 부분을 먹는다. 게임은 나머지 부분으로 계속된다.
- 자르기는 X, Y, Z 축 중 하나를 따라 자르는 방식으로 이루어진다.
- 자신의 차례에 움직일 수 없는 플레이어가 게임에서 진다.
두 플레이어가 최적으로 둔다고 가정할 때, 누가 이기는지 구하시오.
입력
프로그램은 하나 이상의 테스트 케이스에 대해 채점된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 하나의 정수로 주어진다. (1 ≤ T ≤ 100)
각 테스트 케이스는 네 개의 공백으로 구분된 정수를 포함하는 한 줄로 시작한다.
- X: 직육면체의 길이 (1 ≤ X ≤ 1,000,000,000)
- Y: 직육면체의 너비 (1 ≤ Y ≤ 1,000,000,000)
- Z: 직육면체의 높이 (1 ≤ Z ≤ 1,000,000,000)
- N: 독성 세포의 수 (0 ≤ N ≤ 100)
이어서 N개의 줄이 주어지며, 각 줄에는 세 개의 공백으로 구분된 정수가 있다.
- xi: i번째 큐브의 x좌표 (1 ≤ xi ≤ X)
- yi: i번째 큐브의 y좌표 (1 ≤ yi ≤ Y)
- zi: i번째 큐브의 z좌표 (1 ≤ zi ≤ Z)
출력
각 테스트 케이스마다 Alice가 이기면 'Alice'를, 그렇지 않으면 'Bob'을 한 줄에 출력한다.
힌트
아래 그림은 첫 번째 테스트 케이스의 예시이다.
