积分: 900 点
问题陈述
玩家 Alice 和 Bob 使用序列玩游戏 L 和 R 长度 N,如下。
- 游戏包括 N 转。
- If i 为奇数,转 i 由Alice扮演;如果 i 为偶数,转 i 由鲍勃扮演。
- 最初,有一堆装有一定数量的石头。
- 对于 i=1,2,\dots,N 按照此顺序,它们执行以下操作(称为转 i):
- 进行回合的玩家 i 之间取整数个石子 L_i 和 R_i,包含在内,来自堆。
- 如果玩家不能拿走满足上述条件的棋子,他们就输了,另一位玩家获胜。
- 如果回合结束时双方都没有输 N,比赛以平局结束。
游戏开始前,双方玩家都会被告知顺序 L 和 R 以及游戏开始时堆中石子的数量。
可以证明该游戏恰好具有以下三种之一 后果:
Alice...爱丽丝有一个获胜策略。Bob...鲍勃有一个制胜策略。Draw...两位玩家都没有获胜策略。
答案 Q 有关此游戏的查询。的 i第查询如下:
- 假设该堆包含 C_i 游戏开始时的棋子。汇报比赛结果:
Alice,Bob,或Draw.
约束
- N, L_i, R_i, Q,和 C_i 是整数。
- 1 \le N \le 3 \times 10^5
- 1 \le L_i \le R_i \le 10^9
- 1 \le Q \le 3 \times 10^5
- 1 \le C_i \le \sum_{i=1}^{N} R_i
输入
输入由标准输入按以下格式给出:
N L_1 R_1 L_2 R_2 \vdots L_N R_N Q C_1 C_2 \vdots C_Q
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
4 1 3 1 2 3 4 1 2 11 1 2 3 4 5 6 7 8 9 10 11
示例输出 1
Alice Alice Alice Bob Bob Alice Alice Alice Draw Draw Draw
该输入包含 11 查询。
- 当 C_i \le 3, Alice 可以拿走所有 C_i 转牌石子 1,堆里没有留下任何石头,所以爱丽丝有一个获胜的策略。
- 当 4 \le C_i \le 5,鲍勃有一个制胜策略。
- 当 6 \le C_i \le 8,爱丽丝有一个获胜的策略。
- 当 C_i \ge 9,两位玩家都没有获胜策略。
- 例如,如果
牌匾上写着 C_i=9,游戏可以按如下方式进行:
- 开启 1,爱丽丝采取 3 石头。 6 石头依然存在。
- 开启 2,鲍勃采取 1 石头。 5 石头依然存在。
- 开启 3,爱丽丝采取 4 石头。 1 石头遗迹。
- 开启 4,鲍勃采取 1 石头。没有留下任何石头。
- 由于到回合结束时双方都没有输 4,比赛以平局结束。
- 各种其他进展都是可能的,但可以证明,当 C_i=9,双方都没有获胜策略(如果双方都发挥最佳,则游戏将以平局结束)。
- 例如,如果
牌匾上写着 C_i=9,游戏可以按如下方式进行: