406801: GYM102562 B Bitwise Party

There is a party in town and you would like to attend it. The party theme is bitwise operations! You just knocked on the door and the bodyguard with a big xor-like hat on his head asks you a question in order to let you in. You just heard your favourite song "Se misca pe bit" playing inside, so you need to solve the problem as quick as possible.

You are given a sequence of $$$1 \leq N \leq 10^6$$$ pairwise distinct non-negative integers $$$a_1, a_2, ..., a_N$$$. The value of a subsequence $$$a_i, a_{i+1}, ..., a_j$$$ with $$$i \leq j$$$ is:

where OR is the bitwise OR operator.

You need to calculate the bitwise XOR sum of the values of all subsequences.

The first line of the input will contain the number $$$N$$$ ($$$1 \leq N \leq 10^6$$$), representing the size of the given sequence $$$a$$$. The following line will contain $$$N$$$ pairwise distinct non-negative integers (the array $$$a$$$), where $$$0 \leq a_i \leq 10^{18}$$$ for $$$1 \leq i \leq N$$$.

You should output one line containing one non-negative integer: the bitwise XOR sum of the values of all subsequences.

4
2 1 5 7

5

The value of subsequence:

$$$[2]$$$ is $$$2 \ \textrm{OR} \ 2 = 2$$$

$$$[2, 1]$$$ is $$$2 \ \textrm{OR} \ 1 = 3$$$

$$$[2, 1, 5]$$$ is $$$5 \ \textrm{OR} \ 1 = 5$$$

$$$[2, 1, 5, 7]$$$ is $$$7 \ \textrm{OR} \ 1 = 7$$$

$$$[1]$$$ is $$$1 \ \textrm{OR} \ 1 = 1$$$

$$$[1, 5]$$$ is $$$5 \ \textrm{OR} \ 1 = 5$$$

$$$[1, 5, 7]$$$ is $$$7 \ \textrm{OR} \ 1 = 7$$$

$$$[5]$$$ is $$$5 \ \textrm{OR} \ 5 = 5$$$

$$$[5, 7]$$$ is $$$7 \ \textrm{OR} \ 5 = 7$$$

$$$[7]$$$ is $$$7 \ \textrm{OR} \ 7 = 7$$$

And the XOR sum of these values is $$$5$$$.