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

/*
 * author:yanghui
 */
public class C {

	class FastIO {
		BufferedReader br;
		StringTokenizer st;
		PrintWriter out;

		public FastIO(File in, File o) {
			try {
				br = new BufferedReader(new FileReader(in));
				out = new PrintWriter(new FileWriter(o));
			} catch (Exception e) {
				e.printStackTrace();
			}
			eat("");
		}

		public FastIO() {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(new OutputStreamWriter(System.out));
			eat("");
		}

		public void eat(String s) {
			st = new StringTokenizer(s);
		}

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

		public boolean hasNext() {
			while (!st.hasMoreTokens()) {
				String s = nextLine();
				if (s == null)
					return false;
				eat(s);
			}
			return true;
		}

		public String next() {
			hasNext();
			return st.nextToken();
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public void print(String ans) {
			out.print(ans);
			out.flush();
		}

		public void print(int ans) {
			out.print(ans);
			out.flush();
		}

		public void print(long ans) {
			out.print(ans);
			out.flush();
		}

		public void print(double ans) {
			out.print(ans);
			out.flush();
		}

		public void println(String ans) {
			out.println(ans);
			out.flush();
		}

		public void println(int ans) {
			out.println(ans);
			out.flush();
		}

		public void println(long ans) {
			out.println(ans);
			out.flush();
		}

		public void println(double ans) {
			out.println(ans);
			out.flush();
		}

		public void println() {
			println("");
			out.flush();
		}

		public void printf(String arg0, Object... arg1) {
			out.printf(arg0, arg1);
			out.flush();
		}

		public void println(int[] ans) {
			for (int i = 0; i < ans.length; i++)
				print(ans[i] + " ");
			println();
		}

		public void println(long[] ans) {
			for (int i = 0; i < ans.length; i++)
				print(ans[i] + " ");
			println();
		}

		public void println(double[] ans) {
			for (int i = 0; i < ans.length; i++)
				print(ans[i] + " ");
			println();
		}

		public void println(Object... ans) {
			for (Object cur : ans)
				print(cur.toString() + " ");
			println();
		}

		public void println(Object ans[][]) {
			for (int i = 0; i < ans.length; i++) {
				for (int j = 0; j < ans[i].length; i++) {
					print(ans[i] + " ");
				}
				println();
			}
		}

		public void println(int ans[][]) {
			for (int i = 0; i < ans.length; i++) {
				for (int j = 0; j < ans[i].length; i++) {
					print(ans[i] + " ");
				}
				println();
			}
		}

		public void println(long ans[][]) {
			for (int i = 0; i < ans.length; i++) {
				for (int j = 0; j < ans[i].length; i++) {
					print(ans[i] + " ");
				}
				println();
			}
		}

		public void println(double ans[][]) {
			for (int i = 0; i < ans.length; i++) {
				for (int j = 0; j < ans[i].length; i++) {
					print(ans[i] + " ");
				}
				println();
			}
		}

		public void println(List<Object> ans) {
			for (Object i : ans) {
				print(i.toString() + " ");
			}
			println();
		}

		public void close() {
			out.flush();
			out.close();
		}
	}

//	FastIO scan = new FastIO(new File("in"), new File("out"));

	 FastIO scan = new FastIO();

	public void run() {

		int n = scan.nextInt();
		int init[] = new int[n + 1];
		int a[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			init[i] = init[i - 1] ^ i;
		}
		for (int i = 1; i <= n; i++) {
			a[i] = scan.nextInt();
		}
		int result = 0;
		for (int i = 1; i <= n; i++) {
			result ^= a[i];
			result ^= init[n % i];
			if ( n / i % 2 == 1) {
				result ^= init[i - 1];
			}
		}
		scan.println(result);
		scan.close();
	}

	public static void main(String args[]) throws Exception {
		new C().run();
	}
}