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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Locale;
import java.util.Map.Entry;

import java.util.Random;
import java.util.Scanner;
import java.util.TreeSet;

public final class CF_626_D2_D {


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}

	//static long mod=1000000007;
	static long mod=998244353 ; 
	

	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static class Composite implements Comparable<Composite>{
		int v;
		int idx;

		public int compareTo(Composite X) {
			if (v!=X.v)
				return v-X.v;
			return idx-X.idx;
		}

		public Composite(int v, int idx) {
			this.v = v;
			this.idx = idx;
		}




	}
	
	static void test() {
		log("testing");
		Random r=new Random();
		int NMAX=100000;
		int VMAX=256;
		int AMAX=1000;
		int BMAX=1000;
		int CMAX=123453;
		int NTESTS=10000000;
		for (int t=0;t<NTESTS;t++) {
			log("------------");
			int n=r.nextInt(NMAX);
			int[] a=new int[n];
			for (int i=0;i<n;i++) {
				a[i]=r.nextInt(AMAX)*r.nextInt(BMAX)+r.nextInt(CMAX);
				
			}
			long y=solveSubtil(a);
			
			long x=solveBourrin(a);
			if (x!=y) {
				log("Error");
				log(n);
				log(a);
				log(x);
				log(y);
				log("good:"+x+"  bad:"+y);
				return;
			}
			
		}
		log("done");
	}

	
	static void test3() {
		log("test 3");
		int VX=12;
		
		for (int a=0;a<VX;a++)
			for (int b=0;b<VX;b++)
				for (int c=0;c<VX;c++)
					for (int d=0;d<VX;d++)
						for (int e=0;e<VX;e++)
						for (int f=0;f<VX;f++)
						{
							int[] ar=new int[] {a,b,c,d,e,f};
							long x=solveBourrin(ar);
							long y=solveSubtil(ar);
							if (x!=y) {
								log("error");
								log(ar.length);
								log(ar);
								log(x);
								log(y);
								return;
							}
						}
				
		
		log("done");
				
	}
	
	static void test2() {
		log("test 3");
		int VX=8;
		
		for (int a=0;a<VX;a++)
			for (int b=0;b<VX;b++)
				for (int c=0;c<VX;c++)
					for (int d=0;d<VX;d++)
						for (int e=0;e<VX;e++)
						for (int f=0;f<VX;f++)
							for (int g=0;g<VX;g++)
								for (int h=0;h<VX;h++)
										
							
						{
							int[] ar=new int[] {a,b,c,d,e,f,g,h};
							long x=solveBourrin(ar);
							long y=solveSubtil(ar);
							if (x!=y) {
								log("error");
								log(ar.length);
								log(ar);
								log(x);
								log(y);
								return;
							}
						}
				
		
		log("done");
				
	}
	
	static long solveBourrin(int[] a) {
		
		int res=0;
		int n=a.length;
		for (int i=0;i<n;i++)
			for (int j=i+1;j<n;j++) {
				int x=a[i]+a[j];
				res^=x;
			}
		return res;
	}
	
	static int CX=29;

	static long solveSubtil(int[] a) {
		//log("solving for");
		//log(a);
		int n=a.length;
		long res=0;
		for (int e=0;e<CX;e++) {
			//log("==============e:"+e);
			int[] b=new int[n];
			int msk=(1<<(e+1))-1;
			int target=1<<e;
			for (int i=0;i<n;i++) {
				b[i]=a[i]&msk;
			}
			Arrays.sort(b);
			// how many 1 ?
			int u=n-1;
			int v=n-1;
			int w=n-1;
			int cn=0;
			//logWln("b:");
			//log(b);
			for (int i=0;i+1<n;i++) {
				int lo=target-b[i];
				if (u<=i)
					u=i+1;
				while (u-1>i && b[u-1]>=lo)
					u--;
				
				int hi=msk-b[i];
				int lo2=target+(target<<1)-b[i];
				if (v<=i)
					v=i+1;
				while (v-1>i && b[v]>hi)
					v--;
				
				if (w<=i)
					w=i+1;
				while (w-1>i && b[w-1]>=lo2)
					w--;
			
				
				//log("b:"+b[i]+" lo:"+lo+" hi:"+hi);
				
				
				//log("u:"+u+" v:"+v);
				if (b[u]>=lo && b[v]<=hi && v>=u) {
					cn+=v-u+1;
				}
				//log("lo2:"+lo2+" w:"+w+" b[w]:"+b[w]);
				if (b[w]>=lo2)
					cn+=n-w;
				cn%=2;
				
			}
			//log("cn:"+cn);
			if (cn%2==1) 
				res+=target;
			
		}
		//log("res:"+res);
		return res;
	}
	
	
	
	static void process() throws Exception {

		//test();
		
		Locale.setDefault(Locale.US);
		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);


	

		int n=reader.readInt();
		int[] a=new int[n];
		for (int i=0;i<n;i++) {
			a[i]=reader.readInt();
		}
		
		//output(solveBourrin(a));
		output(solveSubtil(a));
		
		try {
			out.close();
		} catch (Exception E) {
		}

	}

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

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}