Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

$$$ (a_1 + a_2) ⊕ (a_1 + a_3) ⊕ … ⊕ (a_1 + a_n) \\\ ⊕ (a_2 + a_3) ⊕ … ⊕ (a_2 + a_n) \\\ … \\\ ⊕ (a_{n-1} + a_n) \\\ $$$

Here x ⊕ y is a bitwise XOR operation (i.e. x ^ y in many modern programming languages). You can read about it in Wikipedia: <https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation>.

Input

The first line contains a single integer n (2 ≤ n ≤ 400 000) — the number of integers in the array.

The second line contains integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7).

Output

Print a single integer — xor of all pairwise sums of integers in the given array.

Examples

Input


2
1 2


Output


3

Input


3
1 2 3


Output


2

Note

In the first sample case there is only one sum 1 + 2 = 3.

In the second sample case there are three sums: 1 + 2 = 3, 1 + 3 = 4, 2 + 3 = 5. In binary they are represented as 011_2 ⊕ 100_2 ⊕ 101_2 = 010_2, thus the answer is 2.

⊕ is the bitwise xor operation. To define x ⊕ y, consider binary representations of integers x and y. We put the i-th bit of the result to be 1 when exactly one of the i-th bits of x and y is 1. Otherwise, the i-th bit of the result is put to be 0. For example, 0101_2   ⊕   0011_2 = 0110_2.
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Locale;
import java.util.StringTokenizer;

public class Solution implements Runnable {
	
	private static final int MAXA = 10000000;
	
	private PrintStream out;
	private BufferedReader in;
	private StringTokenizer st;
	
	public void solve() throws IOException {
		long time0 = System.currentTimeMillis();
		
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		int answer = solve(n, a);
		out.println(answer);
		
		System.err.println("time: " + (System.currentTimeMillis() - time0));
	}
	
	private int solve(int n, int[] a) {
		int answer = 0;
		int[] abuf = new int[n];
		for (int bit = 0; (1 << bit) <= 2 * MAXA; bit++) {
			if (solveBit(bit, n, a, abuf)) {
				answer |= (1 << bit);
			}
		}
		return answer;
	}

	private boolean solveBit(int bit, int n, int[] a, int[] abuf) {
		sortBit(bit, n, a, abuf);
		for (int i = 0; i < n; i++) {
			abuf[i] = a[i] & ((1 << (bit + 1)) - 1);
		}
		boolean result = false;
		int to1 = 0;
		int to2 = 0;
		int to3 = 0;
		for (int i = 0; i < n; i++) {
			int j1 = binSearch(abuf, 0, to1, (1 << bit) - abuf[i]);
			int j2 = binSearch(abuf, j1, to2, (2 << bit) - abuf[i]);
			int j3 = binSearch(abuf, j2, to3, (3 << bit) - abuf[i]);
			to1 = j1 + 1;
			to2 = j2 + 1;
			to3 = j3 + 1;
			int cnt01 = j2 - j1;
			int cnt11 = i - j3;
			if (((cnt01 + cnt11) % 2) == 1) {
				result = !result;
			}
		}
		return result;
	}

	private int binSearch(int[] a, int from, int to, int val) {
		int l = from - 1;
		int r = to;
		while (l + 1 < r) {
			int m = (l + r) / 2;
			if (a[m] < val) {
				l = m;
			} else {
				r = m;
			}
		}
		return r;
	}

	private void sortBit(int bit, int n, int[] a, int[] abuf) {
		int cnt0 = 0;
		for (int i = 0; i < n; i++) {
			if ((a[i] & (1 << bit)) == 0) {
				cnt0++;
			}
		}
		int cnt1 = cnt0;
		cnt0 = 0;
		for (int i = 0; i < n; i++) {
			if ((a[i] & (1 << bit)) == 0) {
				abuf[cnt0++] = a[i];
			} else {
				abuf[cnt1++] = a[i];
			}
		}
		flushBuf(a, abuf);
	}

	private void flushBuf(int[] a, int[] abuf) {
		for (int i = 0; i < a.length; i++) {
			a[i] = abuf[i];
		}
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	public String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return null;
			}
			st = new StringTokenizer(line);
		}
		return st.nextToken();
	}
	
	@Override
	public void run() {
		try {
			solve();
			out.close();
		} catch (Throwable e) {
			throw new RuntimeException(e);
		}
	}
	
	public Solution(String name) throws IOException {
		Locale.setDefault(Locale.US);
		if (name == null) {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintStream(new BufferedOutputStream(System.out));
		} else {
			in = new BufferedReader(new InputStreamReader(new FileInputStream(name + ".in")));
			out = new PrintStream(new BufferedOutputStream(new FileOutputStream(name + ".out")));
		}
		st = new StringTokenizer("");
	}
	
	public static void main(String[] args) throws IOException {
		new Thread(new Solution(null)).start();
	}
}
