AT_arc174_f [ARC174F] Final Stage

[problemUrl]: https://atcoder.jp/contests/arc174/tasks/arc174_f プレイヤーである 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_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $ $ Q $ $ C_1 $ $ C_2 $ $ \vdots $ $ C_Q $

全体で $ Q $ 行出力せよ。 そのうち $ i $ 行目には、 $ i $ 個目の質問に対する答えを出力せよ。

### 制約 - $ 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 $ ### Sample Explanation 1 この入力には $ 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 $ のときどちらにも必勝法が無い (両者が勝利に対し最善を尽くした場合、ゲームは引き分けで終了する) ことが示せます。