Description

Given a sequence $A_1, A_2, ..., A_N$ of length $N$, find the sum of the pairwise XOR of all elements in the sequence.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain a positive integer $A_i$.

Output Format

Output one integer on a single line, representing the sum after taking XOR over all unordered pairs.

2
19
10

25

3
7
3
5

12

5
9
13
1
9
6

84

Hint

Sample 2 Explanation

$A_1 ⊕ A_2 = 4$, $A_1 ⊕ A_3 = 2$, $A_2 ⊕ A_3 = 6$, and $4 + 2 + 6 = 12$, so the answer is $12$.

Constraints

For $100\%$ of the testdata, $1 \le N \le 10^6$ and $1 \le A_i \le 10^6$.

Notes

The score of this problem follows the original COCI setting, with a full score of $110$.

This problem is translated from COCI2011-2012 CONTEST #1 T3 X3.

Translated by ChatGPT 5