Let's Play Nim

AtCoder

IDarc105_d

Time2000ms

Memory256MB

Difficulty—

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: 1. 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.) 2. 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$ [samples]

Samples

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

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.

API Response (JSON)

{
  "problem": {
    "name": "Let's Play Nim",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc105_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\nTaro the first and Jiro the second will play...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments