分数: 700 点
问题陈述
Alice 和 Bob 将玩一个游戏。
最初,Alice 和 Bob 各有 N 卡,带有 iAlice 的第张牌具有整数 上面写着 A_i ,并且 iBob 的第张牌具有整数 B_i 。
游戏进行如下:
- 准备一块黑板,上面什么也没有写。
- Alice 吃掉了她的一张牌,并将吃掉的牌上的整数写在黑板上。
- 接下来,鲍勃吃掉了他的一张牌,并将吃掉的牌中的整数写在黑板上。
- 最后,爱丽丝又吃掉了一张卡片,并将吃掉的卡片上的整数写在黑板上。
如果可以用黑板上写的三个整数的边长形成一个(非退化)三角形,则爱丽丝获胜;否则,鲍勃获胜。
当两名玩家都表现最佳时确定谁获胜。
解决每个问题 T 给出的测试用例。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
- 所有输入值均为整数。
- 总和 N 单个输入中的所有测试用例最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N A_1 \ldots A_N B_1 \ldots B_N
输出
打印 T 行。的 i第行 (1 \leq i \leq T) 应包含 Alice 如果爱丽丝赢得了 i第一个测试用例,以及 Bob 如果鲍勃获胜。
示例输入 1
3 3 1 2 3 4 5 6 4 6 1 5 10 2 2 4 5 10 3 1 4 1 5 9 2 6 5 3 2 7 1 8 2 8 1 8 2 8
示例输出 1
Bob Alice Alice
例如,在第一个测试用例中,游戏可以按如下方式进行:
- 爱丽丝吃掉了卡片 上面写着 2 并写着 黑板上的 2 。
- 鲍勃吃掉了卡片 4 并写着 黑板上的 4 。
- 爱丽丝吃掉了卡片 上面写着 1 并写着 黑板上的 1 。
- 黑板上写的数字是 2, 4, 1。不存在有边长的三角形 2, 4, 1,所以鲍勃获胜。
对于这个测试用例,上述过程对于玩家来说不一定是最佳的,但可以证明如果两个玩家都表现最佳,Bob 将获胜。