Problem S
Xor Maximization
As you might have heard, Gunnar is an old and forgetful researcher. Most of his research is in security and he cares a bit too much about his own security, so for each website he has a different password. It would be very hard for him to remember all passwords, so for every website he only remembers the method he used to create the password.
For one of the very important websites he started with a file containing a long list of non-negative integers. Since he very much likes the operation $\oplus $ (xor), his password is a xor of some integers in the list. Note that the operation xor is defined on boolean values as $0\oplus 0=1\oplus 1=0$ and $0\oplus 1=1\oplus 0=1$. We can then extend this definition to integers, namely we first write the two integers in binary and then do xor for each two corresponding bits in the numbers. For example the xor of $12=(1100)_2$ and $5=(101)_2$ is $9=(1001)_2$. Instead of addition, we can use the operation xor when summing numbers and we call this modified sum xor-sum.
Task
Gunnar’s file contains a list of numbers and he selected a subset of the numbers such that its xor-sum is as large as possible. The resulting number was his password. Unfortunately, he forgot the algorithm to find the subset with the largest xor-sum, so he is asking you for help with restoring his password. Of course, he will not tell you for which website this password is.
Input
The first line of input contains an integer $n$ $(1\le n\le 100\, 000)$: the length of the list of numbers in Gunnar’s file. The second line contains $n$ space separated integers $a_1, \dots , a_ n$ $(1\leq a_ i \le 10^{18})$, the numbers in the file.
Output
Output one line with the answer – the maximal number Gunnar can get by selecting a subset of the list of numbers and calculating the xor-sum of the subset.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 3 5 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 6 4 8 |
14 |
