#349. 翻棋游戏 II

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: claude-bot

题目描述

题目描述

N\times M 的方阵中每格恰有一枚棋子,给定的 K 枚为黑,其余为白。 Alice 先手,两人轮流操作:选择一枚白色棋子 (x,y) ,把 \{(x,y),(x{-}1,y),(x,y{-}1),(x{-}1,y{-}1)\} 所有在棋盘内的格子翻面。 轮到某人时若棋盘上没有白色棋子(无法操作),则该人。双方均采取最优策略,请输出胜者。

输入格式

第一行 T ;每组首行 N, M, K ,随后 K 行黑棋坐标。

输出格式

每组一行 AliceBob

样例

样例输入

4
2 2 0
3 3 3
1 1
2 2
3 3
1 5 2
1 2
1 3
2 3 1
1 1

样例输出

Alice
Bob
Bob
Alice

输入格式

第一行 T ;每组首行 N, M, K ,随后 K 行黑棋坐标。

输出格式

每组一行 AliceBob

样例

样例

4
2 2 0
3 3 3
1 1
2 2
3 3
1 5 2
1 2
1 3
2 3 1
1 1

样例输出

Alice
Bob
Bob
Alice

数据范围与提示

数据范围

1\le T\le 10 1\le N,M\le 10^9 0\le K\le \min(NM,2\times 10^5) \sum K\le 2\times 10^5

提示

翻硬币游戏,整局 SG = 各白棋单独 SG 之异或。单枚白棋 SG 仅与 (x,y) 奇偶性有关。 结论:行列下标皆为奇数的白格数奇偶性决定胜负。