XOR Poker

Time limit2sMemory limit512 MB

Summary

Given N integers, choose a nonempty subset of even size whose XOR is maximum and print that value.

Level: Hard8 of 10
Topics: Bit manipulation, Greedy, Math
Solved: No attempts yet

Problem

Jinbyeok and Miya are playing a game called XOR Poker. Each player receives N cards with integers written on them, picks some of the cards, and computes a score. The player with the higher score wins.

The score is computed as follows.

Choose an even number of the given cards. (You cannot choose 0 cards.)
The score is the XOR of the numbers on the chosen cards. (The definition of the XOR of several integers is given in the Hint below.)

For example, suppose Miya holds the cards {1, 2, 3, 3, 5}. If she chooses {2, 3, 3, 5}, the score is 2 $\oplus$ 3 $\oplus$ 3 $\oplus$ 5 = 7. The set {1, 3, 5}, which also gives 7, has an odd number of cards, so it cannot be chosen.

Miya is fiercely competitive and wants to beat Jinbyeok no matter what. Help Miya win the match.

Input

The first line gives N, the number of cards Miya has. (2 ≤ N ≤ 100,000)

The next N lines give the number ai on Miya's i-th card. (0 ≤ ai ≤ 1018)

Output

On the first line, print the maximum score Miya can make when playing XOR Poker with the given cards.

Hint

The XOR of positive integers x1, x2, ..., xN is defined as follows.

Let the XOR value be X. When X is written in binary, the 2k place of X is 1 if an odd number of x1, x2, ..., xN have a 1 in the 2k place, and 0 if an even number do.

Examples3

Example 1
Input
```
5
1
2
3
3
5
```
Expected output
```
7
```
Example 2
Input
```
4
8
2
4
1
```
Expected output
```
15
```
Example 3
Input
```
7
765
876
961
315
346
825
283
```
Expected output
```
1010
```