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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main (String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader (inputStream);
		PrintWriter out = new PrintWriter (outputStream);
		TaskC solver = new TaskC ();
		solver.solve (1, in, out);
		out.close ();
	}
	
	static class TaskC {
		public void solve (int testNumber, InputReader in, PrintWriter out) {
/* let's try to find a pattern of mod+xor
 * trying to find pattern after generating a matrix of mod in 3 direction(vertical, horizontal, diagonal):
 * zekono shonkhake tar dara vag korle hoy 0 ebong tar pore za darai vag koro na ken ans she nijei
 * zeikhane nijeke diye vag hoy shekhan theke vertically ekta chokro shuru hoy of 0 to toto-1
 * so khali duita jinish ber korlei hoye zay, ekta holo zeikhane 0 hoy tar pore ki even shonkhok(0) naki odd
 * arekta holo vertical chokro er double length er pore koto baki thake(double length porzonto repetition so 0)
 * dhuro bal eto optimize koreo tle khailam :((, I think I should use the diagonal pattern with the vertical one
 * because vertical if use one that's complexity is o(n^2) thinking only about the worst case*/
			int n = in.nextInt ();
			long[] p = new long[n+5];
			long os = 0;
			int lst = n;
			long[] dp = new long[n+5];
			dp[0] = 0;
			for (int i = 1; i<n; i++) {
				dp[i] = dp[i-1]^i;
			}
			for (int i = 1; i<=lst; i++) {
				if (((lst-i)&1) != 0) {
					os ^= i;
				}
				int os2 = (lst-i+1)%(2*i);
//			System.out.println (os2);
				if (os2>i) {
				/*for (int j = os2-i; j<i; j++) {
					os ^= j;
//					System.out.println (i+":)"+j);
				}*/
					os ^= dp[i-1];
					os ^= dp[os2-i-1];
				}
				else if (os2>0) {
				/*for (int j = 1; j<os2; j++) {
					os ^= j;
//					System.out.println (i+":))"+j);
				}*/
					os ^= dp[os2-1];
				}
			}
			for (int i = 0; i<n; i++) {
				p[i] = in.nextLong ();
				os ^= p[i];
			}
			out.println (os);
	
		/*for (int i = 1; i<=21; i++) {
//			System.out.printf ("%2d		",i);
			for (int j = 1; j<=21; j++) {
//				System.out.printf ("%3d",i%j);
			}
//			System.out.println ();
		}*/
		
		}
		
	}
	
	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;
		
		public InputReader (InputStream stream) {
			reader = new BufferedReader (new InputStreamReader (stream), 32768);
			tokenizer = null;
		}
		
		public String next () {
			while (tokenizer == null || !tokenizer.hasMoreTokens ()) {
				try {
					String str;
					if ((str = reader.readLine ()) != null) tokenizer = new StringTokenizer (str);
					else return null;//to detect eof
				} catch (IOException e) {
					throw new RuntimeException (e);
				}
			}
			return tokenizer.nextToken ();
		}
		
		public int nextInt () {
			return Integer.parseInt (next ());
		}
		
		public long nextLong () {
			return Long.parseLong (next ());
		}
		
	}
}

