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
import java.io.*;
import java.lang.*;
import java.util.*;
import java.math.*;

public class code
{
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 

    public static void main(String args[])throws IOException
	{
        FastReader scn = new FastReader();
        
        int n = scn.nextInt();
        int p_xor = 0;

        int[] i_xor = new int[n+1];

        for(int i = 1; i <=n ; i++)
        {
            p_xor = p_xor ^ scn.nextInt();
            i_xor[i] = i_xor[i-1] ^ i;
        }

        for(int i = 1; i <= n; i++)
        {
            int cycle_length = 2*i;
            int length_left = n % cycle_length;

            if(length_left == 0)
                continue;

            if(length_left < i)
            {
                p_xor = p_xor ^ i_xor[n%i];
            }
            else if(length_left == i)
            {
                p_xor = p_xor ^ i_xor[i-1];
            }
            else
            {
                p_xor = p_xor ^ i_xor[i-1] ^ i_xor[n%i];
            }
        }
        System.out.println(p_xor);
	}  

  
    public static int getIndex(int[] list, int value, int l, int r)
    {
        while( l <= r)
        {
            int middle = (l+r)/2;

            if(list[middle]==value)
                return middle;
            else if(list[middle] < value)
                l = middle + 1;
            else
                r = middle - 1;
        } 
        return -1;
    }

    public static int getLessThanIndex(ArrayList<Integer> list, int value, int l, int r)
    {
        while( l <= r)
        {
            int middle = (l+r)/2;

            if(list.get(middle)==value)
                return middle;
            else if(list.get(middle) < value)
                l = middle + 1;
            else
                r = middle - 1;
        } 
        return r;
    }

    public static int getMoreThanIndex(ArrayList<Integer> list, int value, int l, int r)
    {
        while( l <= r)
        {
            int middle = (l+r)/2;

            if(list.get(middle)==value)
                return middle;
            else if(list.get(middle) < value)
                l = middle + 1;
            else
                r = middle - 1;
        } 
        return l;
    }

    public static long inverseModulo(long a, long P)
    {
        return powerModulo(a, P-2, P);
    }

    public static long powerModulo(long a, long p, long m)
    {   
        if(p==0)
            return 1;

        long temp = powerModulo(a, p/2, m);
        temp = (temp * temp)%m;
        if(p%2 == 0)
            return temp;
        else
            return (a * temp)%m;

    }
}

class Pair implements Comparable<Pair>
{
    int a, b;

    public Pair(int a, int b)
    {
        this.a = a;
        this.b = b;
    }

    public int compareTo(Pair p)
    {
        return this.b - p.b;
    }
}


class Node
{
    int value;
    int req_value;
    ArrayList<Integer> neighbors;
    boolean visited;

    public Node()
    {
        neighbors = new ArrayList<>();
    }

}

class MutableInt
{
    int count;
    ArrayList<Integer> list;
    public MutableInt()
    {
        list = new ArrayList<>();
    }
}