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.*;
public class C {
	Scanner sc = new Scanner(System.in);

	void doIt() {
		int n = sc.nextInt();
		int Q = 0; // 答え
		// piをすべてをxorする
		for(int i = 0; i < n; i++) Q ^= sc.nextInt();
		// 0からnまでの値の累積を求めておく
		int [] xorsum = new int[n+1];
		for(int i = 1; i < n; i++) xorsum[i] = xorsum[i-1] ^ i; 
		//
		for(int i = 1; i <= n; i++) {
			// 何周するか求める
			int cycle = n / i;
			if(cycle % 2 != 0) { // 奇数ならば1周分
				Q ^= xorsum[i-1];
			} // 偶数ならばその分は0なので何もしない
			int rem = n % i; // 余りの分
			Q ^= xorsum[rem];
		}
		System.out.println(Q);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new C().doIt();
	}

	// thanks to wata
	class Scanner {
		InputStream in;
		byte[] buf = new byte[1 << 10];
		int p, m;
		boolean[] isSpace = new boolean[128];
		Scanner(InputStream in) {
			this.in = in;
			isSpace[' '] = isSpace['\n'] = isSpace['\r'] = isSpace['\t'] = true;
		}
		int read() {
			if (m == -1) return -1;
			if (p >= m) {
				p = 0;
				try {
					m = in.read(buf);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				if (m <= 0) return -1;
			}
			return buf[p++];
		}
		boolean hasNext() {
			int c = read();
			while (c >= 0 && isSpace[c]) c = read();
			if (c == -1) return false;
			p--;
			return true;
		}
		int nextInt() {
			if (!hasNext()) throw new InputMismatchException();
			int c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (c >= 0 && !isSpace[c]);
			return res * sgn;
		}
	}
}
