Problem Background

On a certain perplexing day, CYJian encountered a perplexing problem involving E operations. Finding himself unable to solve it, CYJian decided to start from scratch to study the perplexing E operations.

Problem Description

First, CYJian wrote down a sequence \( a \) of length \( n \).

Then, he came up with the following perplexing expression:

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

CYJian thought this was a simple expression involving E operations and managed to compute the answer in \( 114514 \) seconds using a calculator.

To prove that you can outperform \( 114514 \) CYJians, please compute the value of this expression within \( 1 \) second. You only need to provide the answer modulo \( 2^{32} \).

Input Format

The first line contains a positive integer \( n \), representing the length of the sequence.

The second line contains \( n \) non-negative integers, where the \( i \)-th number represents \( a_i \).

Output Format

A single line containing a non-negative integer, representing the value of the expression given in the problem description.

Sample Input and Output

Input Sample #1

2
1 2

Output Sample #1

30

Input Sample #2

6
1 1 4 5 1 4

Output Sample #2

3944

Input Sample #3

7
1 9 1 9 8 1 0

Output Sample #3

12892

Notes

Explanation of Sample 1:

\[ (1 \ \text{or} \ 1) \ \text{xor} \ (1 \ \text{and} \ 1) = 0 \]
\[ (1 \ \text{or} \ 1) \ \text{xor} \ (1 \ \text{and} \ 2) = 1 \]
\[ (1 \ \text{or} \ 1) \ \text{xor} \ (2 \ \text{and} \ 1) = 1 \]
\[ (1 \ \text{or} \ 1) \ \text{xor} \ (2 \ \text{and} \ 2) = 3 \]
\[ (1 \ \text{or} \ 2) \ \text{xor} \ (1 \ \text{and} \ 1) = 2 \]
\[ (1 \ \text{or} \ 2) \ \text{xor} \ (1 \ \text{and} \ 2) = 3 \]
\[ (1 \ \text{or} \ 2) \ \text{xor} \ (2 \ \text{and} \ 1) = 3 \]
\[ (1 \ \text{or} \ 2) \ \text{xor} \ (2 \ \text{and} \ 2) = 1 \]
\[ (2 \ \text{or} \ 1) \ \text{xor} \ (1 \ \text{and} \ 1) = 2 \]
\[ (2 \ \text{or} \ 1) \ \text{xor} \ (1 \ \text{and} \ 2) = 3 \]
\[ (2 \ \text{or} \ 1) \ \text{xor} \ (2 \ \text{and} \ 1) = 3 \]
\[ (2 \ \text{or} \ 1) \ \text{xor} \ (2 \ \text{and} \ 2) = 1 \]
\[ (2 \ \text{or} \ 2) \ \text{xor} \ (1 \ \text{and} \ 1) = 3 \]
\[ (2 \ \text{or} \ 2) \ \text{xor} \ (1 \ \text{and} \ 2) = 2 \]
\[ (2 \ \text{or} \ 2) \ \text{xor} \ (2 \ \text{and} \ 1) = 2 \]
\[ (2 \ \text{or} \ 2) \ \text{xor} \ (2 \ \text{and} \ 2) = 0 \]

Summing all the results gives the answer \( 30 \).

This problem uses batched tests.

For \( 100\% \) of the test cases: \( 1 \leq n \leq 5 \times 10^5 \), \( 0 \leq a_i \leq 2^{32}-1 \).

This problem consists of \( 6 \) subtasks with the following scores and constraints:

Subtask 1 (1 point): Matches 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 data range.

If you are unfamiliar with the E operation, please refer to this link.

见题面 Input 部分

见题面 Output 部分