{"problem":{"name":"[DMOI-R1] 柯基棋","description":{"content":"小 A 和小 B 在一个 $n \\times n$ 的棋盘内轮流下棋。小 A 先手，小 B 后手。设当前有一只“柯基”被下在了棋盘的 $(x,y)$ 处，那么棋盘内的 $(x-1,y-1)$，$(x-1,y+1)$，$(x+1,y-1)$，$(x+1,y+1)$ 处都会变为这只“柯基”的地盘，也就不能再放一只“柯基”。当一个人不能再放下一只“柯基”时，他就输了。 可惜，小 C 却不怎么喜欢柯基，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8887"},"statements":[{"statement_type":"Markdown","content":"小 A 和小 B 在一个 $n \\times n$ 的棋盘内轮流下棋。小 A 先手，小 B 后手。设当前有一只“柯基”被下在了棋盘的 $(x,y)$ 处，那么棋盘内的 $(x-1,y-1)$，$(x-1,y+1)$，$(x+1,y-1)$，$(x+1,y+1)$ 处都会变为这只“柯基”的地盘，也就不能再放一只“柯基”。当一个人不能再放下一只“柯基”时，他就输了。\n\n可惜，小 C 却不怎么喜欢柯基，所以他很反对小 A 和小 B 玩“柯基”棋，于是他非常喜欢捣乱棋局。当小 A 和小 B 一共下了 $x_i$ 只“柯基”时，小 C 就会以当前 $w \\times w$ 棋盘的中心为中心，扩大棋盘为 $(w+2) \\times (w+2)$，他一共会捣乱 $q$ 次。\n\n而你的任务是要判断这局棋是小 A 赢还是小 B 赢，如果小 A  赢，输出 `A won`，否则输出 `B won`。\n\n由于他们两个人比较贪玩，所以他们一共会玩 $T$ 局。\n\n**注意**：\n\n1. 当小 A 和小 B 已经将原来的棋盘下到不能再下时，他们会直接跳转到小 C 下一次的捣乱（如果有）。\n\n2. 小 A 和小 B 知道小 C 会捣乱，且会按照自己的最优策略走。\n\n由于数据过大，$x_i$ 由数据随机生成器给出。\n\n## Input\n\n第一行一个正整数 $T$，表示 $T$ 组数据。\n\n每组数据一行三个正整数 $n,q,seed$，其中 $seed$ 的作用见提示说明。\n\n## Output\n\n共 $T$ 行，每一行输出一个字符串 `A won` 或 `B won`。\n\n[samples]\n\n## Background\n\n小 A 和小 B 都是爱狗人士，且绝顶聪明，尤其喜爱柯基，于是他们发明了“柯基棋”。\n\n## Note\n\n### 随机数据生成器\n\n每一轮游戏的 $x_i$ 由下方的生成器给出：\n\n```cpp\nunsigned long long x[10000005];\nunsigned long long xor_shift(unsigned long long &seed){\n  return seed^=seed>>12, seed^=seed<<25, seed^=seed>>27, seed*0x2545F4914F6CDD1D;\n}\nint main(){\n  //your code here\n  int n,q;\n  unsigned long long seed;\n  cin>>n>>q>>seed;\n  for(int i=1;i<=q;i++){\n\tx[i]=x[i-1]+((xor_shift(seed)%(unsigned long long)(2*2)+1))*2;\n  }\n  //your code here\n  return 0;\n}\n```\n\n### 样例解释\n\n对于第一局游戏，$x_i$ 数组如下：`6 8 16 18 22`。\n\n对于第二局游戏，$x_i$ 数组如下：`8 14 16 24 32 36 38 40`。\n\n对于第三局游戏，$x_i$ 数组如下：`4 8 10 16`。\n\n### 数据范围\n\n对于 $20\\%$ 的数据，$n,q\\leq100$。\n\n对于 $50\\%$ 的数据，$n,q\\leq10000$。\n\n对于 $100\\%$ 的数据，$1 \\le T \\le 10,2\\leq n,q,\\sum q \\leq 10^7$，$x_i \\equiv 0 \\pmod 2\\ (i\\in[1,q]),0 \\le seed \\le 10^7$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8887","tags":["模拟","博弈论","洛谷原创","O2优化"],"sample_group":[["3\n2 5 493\n3 8 3219\n8 4 1294","B won\nA won\nB won"]],"created_at":"2026-03-03 11:09:25"}}