406801: GYM102562 B Bitwise Party

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Bitwise Partytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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:

$$$\textrm{max}\{a_i, ..., a_j\} \ \textrm{OR} \ \textrm{min}\{a_i, ..., a_j\}$$$

where OR is the bitwise OR operator.

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

Input

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$$$.

Output

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

ExampleInput
4
2 1 5 7
Output
5
Note

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$$$.

加入题单

上一题 下一题 算法标签: