QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
Statistics

给定 $n$ 个非负整数 $a_1, a_2, \cdots, a_N$。

Magic 和 Spark 两个人进行博弈,两个人轮流操作,每次每个人可以从数组的最左边或者最右边拿走一个数,最后所有拿走的数的异或和更大的人获胜。

问两人都采取最优策略,谁会获胜。先手获胜输出 First,后手获胜输出 Second,平局输出 Draw

输入格式

第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 组数据,

每组第一行一个整数 $n$,表示 $a$ 的长度; 接下来一行 $n$ 个整数 $a_1,a_2,\cdots ,a_n$,表示序列 $a$。

输出格式

对于每组数据,输出一行一个字符串表示答案。

样例数据

样例输入

3
2
3 3
2
3 5
3
4 4 4

样例输出

Draw
First
Second

子任务

对于 $100\%$ 的数据,$1 \leq T \leq 40$,$1 \le n \le 5 \times 10^4$,$0 \le a_i < 2^{31}$。

  • Subtask #1(15 points):$n≤15$。
  • Subtask #2(20 points):$n≤10^3$。
  • Subtask #3(25 points):保证每个 $a_i$ 在 $[0,2^{31}−1]$ 范围内均匀随机。
  • Subtask #4(40 points):无特殊限制。