Description

First, CYJian wrote a sequence $a$ of length $n$.

Then he had a sudden idea and wrote down the following puzzling expression:

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n} (a_i\ {\rm or}\ a_j)\ {\rm xor}\ (a_k\ {\rm and}\ a_l)$$

CYJian thought this was a simple expression of “e-operation”, and it took him $114514{\rm s}$ with a calculator to compute the answer.

To prove that you can outperform $114514$ CYJian, please compute the value of this expression within $1{\rm s}$. You only need to output the value modulo $2^{32}$.

Input Format

The first line contains a positive integer $n$, denoting the length of the sequence.

The second line contains $n$ non-negative integers; the $i$-th number is $a_i$.

Output Format

Output one non-negative integer, representing the value of the expression given in the description.

2
1 2

30

6
1 1 4 5 1 4

3944

7
1 9 1 9 8 1 0

12892

Hint

Explanation for Sample 1:

$(1\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 1) = 0$.

$(1\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 2) = 1$.

$(1\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 1) = 1$.

$(1\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 2) = 3$.

$(1\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 1) = 2$.

$(1\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 2) = 3$.

$(1\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 1) = 3$.

$(1\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 2) = 1$.

$(2\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 1) = 2$.

$(2\ {\rm or}\ 1)\ {\rm xor}\ (1\ {\rm and}\ 2) = 3$.

$(2\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 1) = 3$.

$(2\ {\rm or}\ 1)\ {\rm xor}\ (2\ {\rm and}\ 2) = 1$.

$(2\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 1) = 3$.

$(2\ {\rm or}\ 2)\ {\rm xor}\ (1\ {\rm and}\ 2) = 2$.

$(2\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 1) = 2$.

$(2\ {\rm or}\ 2)\ {\rm xor}\ (2\ {\rm and}\ 2) = 0$.

Summing all results, we get the answer $30$.

---

This problem uses bundled testdata.

Constraints: for $100\%$ of the test points, $1 \leq n \leq 5 \times 10^5$, $0 \leq a_i \leq 2^{32}-1$.

There are $6$ subtasks in total. The score and settings for each subtask are as follows:

Subtask $1$ ($1$ point): Sample 1.

Subtask $2$ ($14$ points): $1 \leq n \leq 80$.

Subtask $3$ ($25$ points): $0 \leq a_i \leq 80$.

Subtask $4$ ($30$ points): $0 \leq a_i \leq 5000$.

Subtask $5$ ($25$ points): $1 \leq n \leq 1000$.

Subtask $6$ ($5$ points): no special constraints.

---

Friendly Reminder

Please pay attention to the constraints.

If you do not know what the “e-operation” above is, please refer to here.

Translated by ChatGPT 5