Xor Sum#11819

Xor Sum

4 seconds

128 megabytes

Hard

Print the answer for the following code:

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = i; j <= n; j++) {
            sum += a[j];
            ans ^= sum;
        }
    }
    cout << ans;

C++

Input

The first line contains a single integer $n (1 \leq n \leq 3 \cdot 1 0^{5})$ n~(1 \le n \le 3 \cdot 10^5) — the number of elements in the array.

The second line contains $n$ integers $a_{1}, a_{2}, ..., a_{n} (0 \leq a_{i} \leq 1 0^{9})$ a_1, a_2, ..., a_n~(0 \le a_i \le 10^9).

Output

Print the answer for the given code.

Examples

Example 1