#ARC105D. 一起来玩 Nim

一起来玩 Nim

一起来玩 Nim

时间限制:2s
空间限制:1024MB

题目描述

有 NN 个袋子和 NN 个盘子。袋子 ii 中有 aia_i 枚硬币,所有盘子初始为空。先手与后手轮流行动,先手先行动:

  1. 如果仍有非空袋子,选择一个非空袋子和一个盘子,把袋中全部硬币移到该盘子;
  2. 如果所有袋子都为空,选择一个非空盘子,从中取走至少一枚硬币。

最先无法行动的人失败。两人都采用最优策略,判断胜者。共有 TT 组测试数据。

输入格式

T
N_1
a_{1,1} a_{1,2} ... a_{1,N_1}
...
N_T
a_{T,1} a_{T,2} ... a_{T,N_T}

输出格式

每组数据输出一行。先手获胜输出 First,后手获胜输出 Second。

样例输入 1

3
1
10
2
1 2
21
476523737 103976339 266993 706803678 802362985 892644371 953855359 196462821 817301757 409460796 773943961 488763959 405483423 616934516 710762957 239829390 55474813 818352359 312280585 185800870 255245162

样例输出 1

Second
First
Second

数据范围

  • 1≤T≤1051\le T\le10^5;
  • 1≤N≤1051\le N\le10^5;
  • 1≤ai≤1091\le a_i\le10^9;
  • 单个输入文件中所有 NN 之和不超过 2×1052\times10^5。
子任务编号 分值 特殊限制
1 10 每组数据的 NN 都是奇数
2 14 每组数据中的 aia_i 两两不同
3 18 ai≤20a_i\le20
4 28 每组数据均有 N≤2000N\le2000
5 30 无特殊限制