Problem Description

Given an array $A_i$, compute the XOR sum of every subarray and then sum up all these XOR sums. In other words, for every pair $L, R$ satisfying $1 \leq L \leq R \leq n$, compute the XOR of the elements from the $L$-th to the $R$-th in the array, and output the total sum of the results over all such $L, R$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $A_i$, separated by a single space.

Output Format

Output one line containing an integer representing the answer.

5
1 2 3 4 5

39

Hint

Constraints

For $30\%$ of the testdata, $n \leq 300$.

For $60\%$ of the testdata, $n \leq 5000$.

For all testdata, $1 \leq n \leq 10^5$, $0 \leq A_i \leq 2^{20}$.

Translated by ChatGPT 5