/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 枚の整数が書かれたカードがあります。i 枚目のカードには A_i が書かれています。
Alice と Bob はこの N 枚のカードでゲームをします。最初、すべてのカードは山にあります。Alice を先手として、交互に山からカードがなくなるまで以下の操作を繰り返します。
- 山にあるカードを 1 枚選び、そのカードを山から取り出して自分の手札にする
最終的に、自分の手札の全てのカードに書かれた整数の排他的論理和をスコアとします。スコアが大きい方の人が勝ちです。スコアが同じ時は引き分けとします。
両者が最適に行動したとき、引き分けになるか、引き分けにならないならばどちらが勝つか判定してください。
Q 個のテストケースが与えられるので、それぞれについて答えを求めてください。
排他的論理和とは
整数 a, b の排他的論理和 a \oplus b は、以下のように定義されます。- a \oplus b を二進表記した際の 2^k \, (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, \dots, p_k の排他的論理和は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。
「最適に行動する」とは？
「最適に行動する」とは、以下のように行動することを指します。
- 相手がどのように行動しても自身が勝つようにすることが可能ならば、自身が勝つような行動を行う。
- そうでなく、相手がどのように行動しても自身が負けないようにすることが可能ならば、自身が負けないような行動を行う。
- そうでなければ、無作為に行動を行う。
制約
- 1 \leq Q \leq 2 \times 10^{5}
- 1 \leq N \leq 2 \times 10^{5} (1 \leq i \leq N)
- 0 \leq A_i \leq 10^{18} (1 \leq i \leq N)
- N の総和は 2 \times 10^{5} 以下
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
case_{1}
case_{2}
\vdots
case_{Q}
ここで、case_{i} は i 番目のテストケースを意味する。
各テストケースは以下の形式で与えられる。
N
A_{1} A_{2} \ldots A_{N}
出力
それぞれのテストケースについて、引き分けになるなら Draw と、Aliceが勝つなら Alice と、Bobが勝つなら Bob と出力せよ。
入力例 1
3 1 1 2 100 100 3 20090926 20250401 33550336
出力例 1
Alice Draw Bob
1 個目のテストケースについては、以下のような操作が考えられます。
Alice が 1 のカードを自分の手札にします。Alice のスコアが 1 で、Bob のスコアが 0 となり、Alice の勝ちです。
2 個目のテストケースについては、以下のような操作が考えられます。
Alice が 100 のカードを自分の手札にします。次に、Bob が 100 のカードを自分の手札にします。Alice のスコアが 100 で、Bob のスコアが 100 となり、引き分けになります。