F - Final Stage Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

プレイヤーである 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 とゲーム開始時点で山にある石の個数 は知らされています。

このとき、このゲームは以下の 3 通りの 解析結果 のうち丁度ひとつに当てはまることが証明できます。

  • Alice ... Alice に必勝法が存在する。
  • Bob ... 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 のとき、 1 ターン目で Alice が C_i 個の石を取って山に残る石を 0 個にできるので、 Alice に必勝法が存在します。
  • 4 \le C_i \le 5 のとき、 Bob に必勝法が存在します。
  • 6 \le C_i \le 8 のとき、 Alice に必勝法が存在します。
  • 9 \le 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 のときどちらにも必勝法が無い (両者が勝利に対し最善を尽くした場合、ゲームは引き分けで終了する) ことが示せます。

Points: 900 points

Problem Statement

Players Alice and Bob play a game using sequences L and R of length N, as follows.

  • The game consists of N turns.
  • If i is odd, turn i is played by Alice; if i is even, turn i is played by Bob.
  • Initially, there is a pile with some number of stones.
  • For i=1,2,\dots,N in this order, they perform the following operation (called turn i):
    • The player who plays turn i takes an integer number of stones between L_i and R_i, inclusive, from the pile.
    • If the player cannot take stones satisfying the above, they lose, and the other player wins.
  • If neither player has lost by the end of turn N, the game ends in a draw.

Before the game starts, both players are informed of the sequences L and R and the number of stones in the pile at the start of the game.

It can be proved that the game has exactly one of the following three consequences:

  • Alice ... Alice has a winning strategy.
  • Bob ... Bob has a winning strategy.
  • Draw ... Neither player has a winning strategy.

Answer Q queries about this game. The i-th query is as follows:

  • Assume that the pile contains C_i stones at the start of the game. Report the consequence of the game: Alice, Bob, or Draw.

Constraints

  • N, L_i, R_i, Q, and C_i are integers.
  • 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

Input

The input is given from Standard Input in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
Q
C_1
C_2
\vdots
C_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

4
1 3
1 2
3 4
1 2
11
1
2
3
4
5
6
7
8
9
10
11

Sample Output 1

Alice
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Draw
Draw
Draw

This input contains 11 queries.

  • When C_i \le 3, Alice can take all C_i stones on turn 1, leaving no stones in the pile, so Alice has a winning strategy.
  • When 4 \le C_i \le 5, Bob has a winning strategy.
  • When 6 \le C_i \le 8, Alice has a winning strategy.
  • When C_i \ge 9, neither player has a winning strategy.
    • For example, if C_i=9, the game could proceed as follows:
      • On turn 1, Alice takes 3 stones. 6 stones remain.
      • On turn 2, Bob takes 1 stone. 5 stones remain.
      • On turn 3, Alice takes 4 stones. 1 stone remains.
      • On turn 4, Bob takes 1 stone. No stones remain.
      • Since neither player has lost by the end of turn 4, the game ends in a draw.
    • Various other progressions are possible, but it can be shown that when C_i=9, neither player has a winning strategy (if both players play optimally, the game will end in a draw).