[DMOI-R1] 柯基棋

小 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 却不怎么喜欢柯基，所以他很反对小 A 和小 B 玩“柯基”棋，于是他非常喜欢捣乱棋局。当小 A 和小 B 一共下了 $x_i$ 只“柯基”时，小 C 就会以当前 $w \times w$ 棋盘的中心为中心，扩大棋盘为 $(w+2) \times (w+2)$，他一共会捣乱 $q$ 次。 而你的任务是要判断这局棋是小 A 赢还是小 B 赢，如果小 A 赢，输出 `A won`，否则输出 `B won`。 由于他们两个人比较贪玩，所以他们一共会玩 $T$ 局。 **注意**： 1. 当小 A 和小 B 已经将原来的棋盘下到不能再下时，他们会直接跳转到小 C 下一次的捣乱（如果有）。 2. 小 A 和小 B 知道小 C 会捣乱，且会按照自己的最优策略走。 由于数据过大，$x_i$ 由数据随机生成器给出。 ## Input 第一行一个正整数 $T$，表示 $T$ 组数据。 每组数据一行三个正整数 $n,q,seed$，其中 $seed$ 的作用见提示说明。 ## Output 共 $T$ 行，每一行输出一个字符串 `A won` 或 `B won`。 [samples] ## Background 小 A 和小 B 都是爱狗人士，且绝顶聪明，尤其喜爱柯基，于是他们发明了“柯基棋”。 ## Note ### 随机数据生成器 每一轮游戏的 $x_i$ 由下方的生成器给出： ```cpp unsigned long long x[10000005]; unsigned long long xor_shift(unsigned long long &seed){ return seed^=seed>>12, seed^=seed<<25, seed^=seed>>27, seed*0x2545F4914F6CDD1D; } int main(){ //your code here int n,q; unsigned long long seed; cin>>n>>q>>seed; for(int i=1;i<=q;i++){ x[i]=x[i-1]+((xor_shift(seed)%(unsigned long long)(2*2)+1))*2; } //your code here return 0; } ``` ### 样例解释 对于第一局游戏，$x_i$ 数组如下：`6 8 16 18 22`。 对于第二局游戏，$x_i$ 数组如下：`8 14 16 24 32 36 38 40`。 对于第三局游戏，$x_i$ 数组如下：`4 8 10 16`。 ### 数据范围 对于 $20\%$ 的数据，$n,q\leq100$。 对于 $50\%$ 的数据，$n,q\leq10000$。 对于 $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$。