We are given an array of length . For a string of length over the alphabet (-indexed), define the "generalized subset sum" as the sum of over all indices that satisfy:
For each , if then the -th bit of is .
For each , if then the -th bit of is .
If there is no restriction on the -th bit of .
For example, when and , the generalized subset sum is (binary and ). Note that the first bit is the lowest bit.
Your task is to compute the generalized subset sum for each string of length over the alphabet . Because the total output can be large, you only need to output the bitwise XOR of all these sums.
输入格式
The first line of the input contains an integer ().
The second line of the input contains integers (), contents in array .
输出格式
Print an integer denoting the bitwise-XOR of all generalized subset sums.
样例
样例输入 1
1
3 5
样例输出 1
14
样例输入 2
2
2 6 8 8
样例输出 2
0
数据范围与提示
The following are query strings and their corresponding generalized subset sums in sample :
