给定 $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):无特殊限制。