XOR Sum 3

Compute the XOR of every contiguous subsequence of A and print the sum of all those XOR values.

Medium6Bit manipulationPrefix sumMathInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples1

The XOR sum of a sequence is the value obtained by XORing all of its elements together.

Given a sequence $A$ , write a program that computes the XOR sum of every contiguous subsequence of $A$ and outputs the total of all those XOR sums.

The first line contains the length $N$ of the sequence. $(1 \le N \le 100\,000)$

The second line contains the $N$ elements of $A$ , separated by spaces. Each element is a non-negative integer not exceeding $10^9$ .

Print the sum of the XOR sums of all contiguous subsequences of $A$ on the first line.