Unfair Nim

AtCoder

IDabc172_f

Time2000ms

Memory256MB

Difficulty—

There are $N$ piles of stones. The $i$\-th pile has $A_i$ stones. Aoki and Takahashi are about to use them to play the following game: * Starting with Aoki, the two players alternately do the following operation: * Operation: Choose one pile of stones, and remove one or more stones from it. * When a player is unable to do the operation, he loses, and the other player wins. When the two players play optimally, there are two possibilities in this game: the player who moves first always wins, or the player who moves second always wins, only depending on the initial number of stones in each pile. In such a situation, Takahashi, the second player to act, is trying to guarantee his win by moving at least zero and at most $(A_1 - 1)$ stones from the $1$\-st pile to the $2$\-nd pile before the game begins. If this is possible, print the minimum number of stones to move to guarantee his victory; otherwise, print `-1` instead. ## Constraints * $2 \leq N \leq 300$ * $1 \leq A_i \leq 10^{12}$ ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $\ldots$ $A_N$ [samples]

Samples

Input #1

2
5 3

Output #1

1

Without moving stones, if Aoki first removes $2$ stones from the $1$\-st pile, Takahashi cannot win in any way.
If Takahashi moves $1$ stone from the $1$\-st pile to the $2$\-nd before the game begins so that both piles have $4$ stones, Takahashi can always win by properly choosing his actions.

Input #2

2
3 5

Output #2

\-1

It is not allowed to move stones from the $2$\-nd pile to the $1$\-st.

Input #3

3
1 1 2

Output #3

\-1

It is not allowed to move all stones from the $1$\-st pile.

Input #4

8
10 9 8 7 6 5 4 3

Output #4

Input #5

3
4294967297 8589934593 12884901890

Output #5

1

Watch out for overflows.

API Response (JSON)

{
  "problem": {
    "name": "Unfair Nim",
    "description": {
      "content": "There are $N$ piles of stones. The $i$\\-th pile has $A_i$ stones. Aoki and Takahashi are about to use them to play the following game: *   Starting with Aoki, the two players alternately do the follo",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc172_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ piles of stones. The $i$\\-th pile has $A_i$ stones.\nAoki and Takahashi are about to use them to play the following game:\n\n*   Starting with Aoki, the two players alternately do the follo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments