G - Min Nim Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 個の石の山があり、はじめ i 番目の山には石が A_i 個あります。これらの山を使って Anna と Bob がゲームを行います。

ゲームでは、Anna を先手として二人が交互に以下の操作を行います。

  • 石が 1 個以上残っている山 i\,(1\leq i \leq N) を選ぶ。山 i から 1 個以上の石を取り除く。ただし、操作後に山 i に残っている石の個数が、各山に残っている石の個数全体の最小値になっている必要がある。より形式的には、以下が成り立つように操作する必要がある。
    • 操作後に山 j に残っている石の数を A'_j とする (残っていなければ A'_j=0 とする)。 A'_i=\min\{A'_1,A'_2,\dots,A'_N\} が成り立つ。

操作が行えなくなった方が負けで、負けなかった方が勝ちです。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T
  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9 \, (i=1,2,\dots,N)
  • 1 つの入力に含まれるテストケースについて、 N の総和は 10^5 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各ケースは以下の形式で与えられる。

N
A_1 A_2 \dots A_N

出力

T 行出力せよ。 i 行目には i 番目のテストケースについて、先手の Anna が勝つ場合 First を、後手の Bob が勝つ場合 Second を出力せよ。

入力例 1

2
3
3 1 4
8
3 1 4 1 5 9 2 6

出力例 1

First
Second

1 番目のテストケースについて、最初に Anna が行うことのできる操作は以下のとおりです。

  • 山 1 から 2 個以上の石を取り除く
  • 山 2 から 1 個以上の石を取り除く
  • 山 3 から 3 個以上の石を取り除く