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 翻译