/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N の番号がついた N 枚の袋と、1 から N の番号がついた N 枚の皿があります。 袋 i には a_i 個のコインが入っています。どの皿もはじめは何も乗っていません。
先手太郎君と後手次郎君が対戦ゲームをします。 先手太郎君と後手次郎君の手番が交互に訪れます。先手太郎君が先手です。 それぞれのプレイヤーは、手番において以下の 2 つの手のどちらかを打つことが可能です。
- (コインが入った袋が 1 つ以上存在するとき)：コインが入った袋と皿を 1 枚ずつ選び、選んだ袋の中に入った全てのコインを選んだ皿に移す(選ぶ皿にはコインが乗っていてもいなくても構わない)
- (コインが入った袋が存在しないとき)：コインが乗った皿を 1 枚選び、選んだ皿から 1 枚以上のコインを取り除く
先に手が打てなくなった人の負けです。2 人が最適に行動したときに勝つのはどちらかを判定してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 与えられる入力は全て整数
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{5}
- 1 \leq a_i \leq 10^9
- 1 つの入力ファイルにおいて、N の総和は 2 \times 10^5 を超えない。
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられる。
N a_1 a_2 \cdots a_N
出力
T 行出力せよ。i 行目には i 番目のテストケースの勝者が先手太郎君ならば 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 では後手次郎君が勝利します。以下はそのような 2 人の行動の例です。
- 先手太郎君の手番では、袋 1 を選んで皿 1 にコインを移すしかできません。
- 後手次郎君の手番で皿 1 を選んで全てのコインを取り除くことで、先手太郎君は手番で手を打つことができず敗北します。
- コインが入った袋が存在するとき、コインの入った袋を選んで皿に移す手しか打てないことに注意してください。
- 同様に、コインが入った袋が存在しないときは皿を選んでコインを 1 つ以上取り除く手しか打てないことに注意してください。
Score : 600 points
Problem Statement
We have N bags numbered 1 through N and N dishes numbered 1 through N. Bag i contains a_i coins, and each dish has nothing on it initially.
Taro the first and Jiro the second will play a game against each other. They will alternately take turns, with Taro the first going first. In each player's turn, the player can make one of the following two moves:
- When one or more bags contain coin(s): Choose one bag that contains coin(s) and one dish, then move all coins in the chosen bag onto the chosen dish. (The chosen dish may already have coins on it, or not.)
- When no bag contains coins: Choose one dish with coin(s) on it, then remove one or more coins from the chosen dish.
The player who first becomes unable to make a move loses. Determine the winner of the game when the two players play optimally.
You are given T test cases. Solve each of them.
Constraints
- All values in input are integers.
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{5}
- 1 \leq a_i \leq 10^9
- In one input file, the sum of N does not exceed 2 \times 10^5.
Input
Input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is in the following format:
N a_1 a_2 \cdots a_N
Output
Print T lines. The i-th line should contain First if Taro the first wins in the i-th test case, and Second if Jiro the second wins in the test case.
Sample Input 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
Sample Output 1
Second First Second
- In test case 1, Jiro the second wins. Below is one sequence of moves that results in Jiro's win:
- In Taro the first's turn, he can only choose Bag 1 and move the coins onto Dish 1.
- In Jiro the second's turn, he can choose Dish 1 and remove all coins from it, making Taro fail to make a move and lose.
- Note that when there is a bag that contains coin(s), a player can only make a move in which he chooses a bag that contains coin(s) and moves the coin(s) onto a dish.
- Similarly, note that when there is no bag that contains coin(s), a player can only make a move in which he chooses a dish and removes one or more coins.