XOR Subarray Sum

You are given an array \(A = [A_1, A_2, \dots, A_n]\). For every subarray defined by indices \(L, R\) (with \(1 \le L \le R \le n\)), compute the XOR of the elements in that subarray, i.e. \(A_L \oplus A_{L+1} \oplus \dots \oplus A_R\). Your task is to calculate the sum over all these subarrays.

Formally, you need to compute:

[ \sum_{1 \le L \le R \le n} \left( A_L \oplus A_{L+1} \oplus \cdots \oplus A_R \right), ]

where \(\oplus\) represents the bitwise XOR operation.

inputFormat

The first line of input contains an integer \(n\) (the number of elements in the array). The second line contains \(n\) space-separated integers \(A_1, A_2, \dots, A_n\).

outputFormat

Output a single integer, which is the sum of the XOR of every subarray.

sample

1
1

1