AT_arc174_f [ARC174F] Final Stage

Alice 和 Bob 作为玩家，使用长度为 $N$ 的数列 $L,R$ 进行如下游戏。 - 游戏共进行 $N$ 回合。 - 当 $i$ 为奇数时，第 $i$ 回合由 Alice 操作；当 $i$ 为偶数时，第 $i$ 回合由 Bob 操作。 - 最初，准备一堆石子。 - 按照 $i=1,2,\dots,N$ 的顺序，依次进行以下操作（称为第 $i$ 回合）： - 在第 $i$ 回合，轮到的玩家必须从石堆中取走不少于 $L_i$ 个且不多于 $R_i$ 个的整数个石子。 - 如果无法满足上述条件取石子，则当前轮到的玩家失败，另一方获胜。 - 若第 $N$ 回合结束时双方都未失败，则游戏以平局结束。 在游戏开始前，双方都已知数列 $L,R$ 以及初始石子的数量。 此时，可以证明该游戏必然属于以下三种**解析结果**之一： - `Alice` …… Alice 存在必胜策略。 - `Bob` …… Bob 存在必胜策略。 - `Draw` …… 双方都不存在必胜策略。 对于本游戏，需要回答 $Q$ 个问题。第 $i$ 个问题如下： - 假设游戏开始时石堆中有 $C_i$ 个石子。请回答该情况下游戏的解析结果，输出 `Alice`、`Bob` 或 `Draw`。

输入通过标准输入给出，格式如下： > $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\cdots$ $L_N$ $R_N$ $Q$ $C_1$ $C_2$ $\cdots$ $C_Q$

共输出 $Q$ 行。 第 $i$ 行输出第 $i$ 个问题的答案。

### 数据范围 - $N, L_i, R_i, Q, C_i$ 均为整数。 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq L_i \leq R_i \leq 10^9$ - $1 \leq Q \leq 3 \times 10^5$ - $1 \leq C_i \leq \sum_{i=1}^{N} R_i$ ### 样例解释 1 本输入包含 $11$ 个问题。 - 当 $C_i \leq 3$ 时，Alice 可以在第 $1$ 回合直接取完所有石子，必胜。 - 当 $4 \leq C_i \leq 5$ 时，Bob 存在必胜策略。 - 当 $6 \leq C_i \leq 8$ 时，Alice 存在必胜策略。 - 当 $9 \leq C_i$ 时，双方都不存在必胜策略。 - 以 $C_i=9$ 为例，游戏过程如下： - 第 $1$ 回合 Alice 取 $3$ 个石子，剩 $6$ 个。 - 第 $2$ 回合 Bob 取 $1$ 个石子，剩 $5$ 个。 - 第 $3$ 回合 Alice 取 $4$ 个石子，剩 $1$ 个。 - 第 $4$ 回合 Bob 取 $1$ 个石子，剩 $0$ 个。 - 第 $4$ 回合结束时双方都未失败，游戏平局。 - 其他情况也可以类似分析。对于 $C_i=9$，可以证明双方都不存在必胜策略（即双方都采取最优策略时，游戏以平局结束）。 由 ChatGPT 4.1 翻译