People in the Tomskaya region like magic formulas very much. You can see some of them below.

Imagine you are given a sequence of positive integer numbers p1, p2, ..., pn. Lets write down some magic formulas:

<image><image>

Here, "mod" means the operation of taking the residue after dividing.

The expression <image> means applying the bitwise xor (excluding "OR") operation to integers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by "^", in Pascal — by "xor".

People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence p, calculate the value of Q.

Input

The first line of the input contains the only integer n (1 ≤ n ≤ 106). The next line contains n integers: p1, p2, ..., pn (0 ≤ pi ≤ 2·109).

Output

The only line of output should contain a single integer — the value of Q.

Examples

Input

3
1 2 3


Output

3
# eople in the Tomskaya region like magic formulas very much. You can see some of them below.

# Imagine you are given a sequence of positive integer numbers p1, p2, ..., pn. Lets write down some magic formulas:



# Here, "mod" means the operation of taking the residue after dividing.

# The expression  means applying the bitwise xor (excluding "OR") operation to integers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by "^", in Pascal — by "xor".

# People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence p, calculate the value of Q.

# Input
# The first line of the input contains the only integer n (1 ≤ n ≤ 106). The next line contains n integers: p1, p2, ..., pn (0 ≤ pi ≤ 2·109).

# Output
# The only line of output should contain a single integer — the value of Q.

# Examples
# inputCopy
# 3
# 1 2 3
# outputCopy
# 3

# Because the XOR operation satisfies the law of exchange,

# So formula 2 = p1 ^ p2 ^ ...... ^ pn ^ (1% 1) ^ (1% 2) ^ ...... (1% n) ^ (2% 1)% (2% 2) ^ ...... ^ (2 % n) ^ ...... ^ (n% 1) ^ (n% 2) ^ ...... ^ (n% n)

#  =p1 ^ p2 ^ ...... ^ pn ^ (1% 1) ^ (2% 1) ^ ... (n% 1) ^ (1% 2) ^ (2% 2) ^ ...... ^ (n% 2 ) ^ ...... ^ (1% n)% (2% n) ^ ...... ^ (n% n)

# And for any positive integer k, (1 ~ n)% k will only have k results of 0 ~ (k-1), so (1% k), (2% k) ... (n% k) It is regular, that is (1% k) ^ (2% k) ^ ... ^ (n% k) is regular.

# For example, when n = 15 and k = 7, the results of (1% k), (2% k) ... (n% k) are shown in the table below.


# According to the XOR principle, a ^ a = 0, 0 ^ a = a; so the XOR results in the two red lines in the figure are 0. So ( 1% 7) ^ (2% 7) ^ ...... ^ (15% 7) = 1;

# Another example is when n = 25 and k = 7. The results of ( 1% 7), (2% 7) ... (25% 7) are shown in the table below.


# So ( 1% 7) ^ (2% 7) ^ ...... ^ (25% 7) = 5 ^ 6 ^ 0 = 3
# Therefore, when dealing with this problem, you can use an array a to save the result of 1 XOR to n, and then enumerate k = 1 ~ n, find out how many entire rows have the remainder 0 ~ (k-1), and finally Calculate the part that is less than one full line.

# Meaning of the questions:

# Give N (1 ~ 10 ^ 6) the number of representatives of N, given p1 ...... pn (0 ~ 2 x 10 ^ 9). Seeking and given two formulas.

 

# Ideas:

# Mathematics. 0 to any number of different or all the same (0 ^ x == x), or any number of different time itself is 0 (x ^ x == 0), the XOR two times itself. (X ^ x ^ x == x). So-column table to observe the law:

# Row

# % 

# Row

#     1	2	3	4	5	6	7	8	9	10
# 1	0	1	1	1	1	1	1	1	1	1
# 2	0	0	2	2	2	2	2	2	2	2
# 3	0	1	0	3	3	3	3	3	3	3
# 4	0	0	1	0	4	4	4	4	4	4
# 5	0	1	2	1	0	5	5	5	5	5
# 6	0	0	0	2	1	0	6	6	6	6
# 7	0	1	1	3	2	1	0	7	7	7
# 8	0	0	2	0	3	2	1	0	8	8
# 9	0	1	0	1	4	3	2	1	0	9
# 10	0	0	1	2	0	4	3	2	1	0
# Can be found, a value of 0 on the diagonal upper triangular elements ranks number. Row to see not see anything, but in a column view, you can see that each module corresponds in cycles. And this period is (n / i), if the cycle is an even number, it becomes 0 can be ignored, if it is odd, the exclusive OR result is 0 ^ 1 ^ ...... ^ i - 1. In addition, if the (n% i) is not equal to 0, also need to be described XOR 1 ^ ...... ^ (n% i) ^ (0) (0 XOR after optional, does not change because the XOR 0 its value, so that the back of the pretreatment polyisocyanate 0 or it is not affected), so a good continuous pretreatment 0 XOR values ​​corresponding to each of n.

# After the deal, according to the period and the remainder of the XOR can be the answer. 

#include <cstdio>
#include <cmath>
#include <algorithm>
 
# using namespace std;
 
# const int MAX = 1000001;
 
# int num[MAX];
 
# void solve () {
#         num[0] = 0;
#         for (int i = 1; i < MAX; ++i)
#                 num[i] = num[i - 1] ^ i;
# }
 
# int main() {
#         int n, ans = 0;
 
#         solve();
 
#         scanf("%d", &n);
 
#         for (int i = 1; i <= n; ++i) {
#                 int a;
#                 scanf("%d", &a);
#                 ans ^= a;
#                 if ((n / i) % 2) ans ^= num[i - 1];
#                 if (n % i) ans ^= num[n % i];
#         }
 
#         printf("%d\n", ans);
 
#         return 0;
# }

import sys, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
def findXOR(n):
    remainder = n%4
    if remainder ==0:
        return n
    elif remainder == 1:
        return 1
    elif remainder ==2:
        return n+1
    else:
        return 0
def solution(list1):
    answer = 0
    length = len(list1)
    for i in range(length):
        answer ^=list1[i]
        modded = i+1
        place = length//modded
        if place%2==0:
            answer ^= findXOR(length%modded)
        else:
            answer ^= findXOR(modded-1) ^ findXOR(length%modded)
    return answer

n = int(input())
list1 = [int(x) for x in input().split()]
print(solution(list1))