← 返回题目列表

Codeforces · 2203/D

D. 除法游戏

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩游戏。它们有一个包含 $$$n$$$ 元素的数组 $$$a$$$ 和一个包含 $$$m$$$ 元素的数组 $$$b$$$。

玩家轮流进行。爱丽丝先走。轮到每个玩家时,从数组 $$$a$$$ 中选择一个数字 $$$x$$$,从数组 $$$b$$$ 中选择一个数字 $$$y$$$。 Alice 有她自己的选择 $$$x$$$ 和 $$$y$$$ 的规则,而 Bob 有他的规则:

  • Alice 必须选择 $$$x$$$ 和 $$$y$$$,使得 $$$y$$$ 能被 $$$x$$$ 整除。
  • Bob 必须选择 $$$x$$$ 和 $$$y$$$ 使得 $$$y$$$ 不是 可被 $$$x$$$ 整除。

选择 $$$x$$$ 和 $$$y$$$ 后,$$$y$$$ 将从数组 $$$b$$$ 中删除(但 $$$x$$$ 保留在 $$$a$$$ 中)。当$$$y$$$从$$$b$$$中删除时,如果$$$y$$$出现多次,则只删除一个。无法采取行动的玩家就输了。

如果双方都发挥最佳,谁会获胜?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^{6}$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{i}$$$ ($$$1 \le a_{i} \le n + m$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的最后一行包含 $$$m$$$ 整数 $$$b_{i}$$$ ($$$1 \le b_{i} \le n + m$$$) — 数组 $$$b$$$ 的元素。

输入的附加限制:

  • 所有测试用例的$$$n$$$总和不超过$$$10^6$$$;
  • 所有测试用例的 $$$m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,打印一个单词:

  • 爱丽丝 如果爱丽丝赢了;
  • 鲍勃 如果鲍勃获胜。

示例

输入
复制

3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5

输出
复制

Alice
Bob
Alice

注意

考虑第一个测试用例。让我们展示一下爱丽丝如何通过动作获胜:

  • 爱丽丝的举动: $$$x = 3, y = 6$$$(此后,$$$6$$$将从$$$b$$$中删除,导致$$$b = [7, 12]$$$)
  • 鲍勃的举动: $$$x = 3, y = 7$$$ (鲍勃无论如何都会选择 $$$y = 7$$$,因为没有 $$$x$$$ 不能整除 $$$y = 12$$$,在此移动之后 $$$b = [12]$$$)
  • 爱丽丝的举动: $$$x = 4, y = 12$$$ (此移动后,$$$b$$$ 变为空)
  • 鲍勃的举动: 鲍勃输了,因为他无法采取行动