Problem7019--ABC172 —— F - Unfair Nim

7019: ABC172 —— F - Unfair Nim

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

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.

Input

Input is given from Standard Input in the following format:
$N$
$A_1\ \ldots\ A_N$

Output

Print the minimum number of stones to move to guarantee Takahashi's win; otherwise, print -1 instead.

Constraints

$2≤N≤300$
$1 \leq A_i \leq 10^{12}$

Sample 1 Input 

2
5 3

Sample 1 Output 

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.

Sample 2 Input 

2
3 5

Sample 2 Output 

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

Sample 3 Input 

3
1 1 2

Sample 3 Output 

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

8
10 9 8 7 6 5 4 3


3

Sample 4 Input 

3
4294967297 8589934593 12884901890

Sample 4 Output 

1

Source/Category

 
Submit