XMAX - XOR Maximization

no tags 

Given a set of integers S = { a1, a2, a3, ... a|S| }, we define a function X on S as follows:
X( S ) = a1 ^ a2 ^ a3 ^ ... ^ a|S|.
(^ stands for bitwise 'XOR' or 'exclusive or')

Given a set of N integers, compute the maximum of the X-function over all the subsets of the given starting set.

Input

The first line of input contains a single integer N, 1 <= N <= 105.
Each of the next N lines contain an integer ai, 1 <= ai <= 1018.

Output

To the first line of output print the solution.

Example

Input:
3
1
2
4

Output:
7

hide comments
Alex Abbas: 2016-04-23 22:41:31

Stick to c++ guys because Input is not formatted properly.

minhthai: 2016-03-09 04:43:42

not easy at all :(

Pratik S: 2015-09-11 16:14:19

are single element subsets accepted? i.e what is the output for:-
3
1
2
7
Is it 7 or 6?

Nishant Gupta: 2015-04-08 14:43:41

nice one :) my 450th on spoj :D

Tejas Sudhir Niphadkar: 2014-12-25 05:43:04

@cc, no it is 3.

RUDRA: 2014-12-16 13:54:06

I think test cases are weak.(I don't know why!!!)
anyone of you realising the same thing??!!

Mohd Rahul Islam: 2014-12-06 09:28:25

@cc fro 1,2,3 answer is 3

Aditya Bahuguna: 2014-01-11 23:28:02

awesome problem!! ;)

Mojtaba FayazBakhsh: 2013-08-05 06:23:08

nice one!
actually same to sgu 275 with a larger n

Arpit: 2013-03-21 20:12:45

Please post some more testcases.


Added by:gustav
Date:2011-01-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:classical problem