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

public class TaskC {

    static Integer[][]dp;
    static int n, m, ans;
    static String s;
    static int[]arr;

    static int dp(int flag, int idx)
    {
        if(idx < 0)
            return 0;
        if(dp[flag][idx] != null)
            return dp[flag][idx] ;

        int take = 0;
        int leave = 0;
        if(flag == 0)
            if(s.charAt(idx) == '1')
            {
                take = arr[idx] + dp(flag, idx - 1);
                leave = dp(1 , idx - 1);
            } else {
                leave = dp(flag , idx - 1);
            }
        else
            take = arr[idx] + dp(flag , idx - 1);

        return dp[flag][idx] = Math.max(take , leave);
    }


    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        n = sc.nextInt();
        arr = new int[n];
        for (int i = 0 ; i < n ; i++)
            arr[i] = sc.nextInt();
        long [] accXOR = new long[n + 1];

        for (int i = 0 ; i <= n ; i++)
        {
            accXOR[i] = i;
            if( i > 0)
                accXOR[i] ^= accXOR[i - 1];
        }

        long ans = 0;

        for (int i = 0 ; i < n ; i++)
        {
            long xor = arr[i];

            if( (n / (i + 1)) % 2 == 0)
            {
                xor ^= accXOR[n%(i + 1)];
            }else{
                xor ^= accXOR[i] ^ accXOR[(n%(i+1))];
            }
            ans^=xor;
        }
        pw.print(ans);
        pw.close();

    }



    private static long gcd(long a, long b) {
        if( b == 0)
            return a;
        return gcd(b  , a%b);
    }

    static long lcm(int a, int b)
    {
        return (a*b)/gcd(a, b);
    }


    private  static int dis(int xa , int ya , int xb , int yb)
    {
        return (xa-xb)*(xa - xb) + (ya- yb)*(ya-yb);
    }


    static class Pair implements Comparable<Pair> {
        double x,y;


        public Pair(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public int compareTo(Pair o) {
           /* if (x == o.x)
                return y - o.y;
            return x - o.x;*/
           return  0;
        }
        public double dis(Pair a){

            return (a.x - x)*(a.x - x) + (a.y-y)*(a.y-y);
        }

        public String toString() {
            return  x+" "+ y;
        }
        public boolean overlap(Pair a)
        {
        if((this.x >= a.x && this.x <= a.y) || (a.x >= this.x && a.x <= this.y)) return true;
            return false;

        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public boolean check() {
            if (!st.hasMoreTokens())
                return false;
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        public double nextDouble() {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() {
            try {
                return br.ready();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }
}