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) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ $$

Here $x \oplus 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 \leq n \leq 400\,000$) — the number of integers in the array.

The second line contains integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 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 \oplus 100_2 \oplus 101_2 = 010_2$, thus the answer is 2.

$\oplus$ is the bitwise xor operation. To define $x \oplus 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 \, \oplus \, 0011_2 = 0110_2$.

Difficulty: HARD

Starter code:

Solutions:
for z in range(1):
	co = 0
	n = int(input())
	l = list(map(int, input().split()))
	for e in range(1, 25):
		po = 2 ** e
		re = sorted([k % po for k in l])
		b = n
		r = 0
		for a in range(n):
			b -= 1
			while re[a] + re[b] >= po and b >= 0:
				b -= 1
			b += 1
			r += n - b - (a >= b)
		r //= 2
		if r % 2:
			co += 2 ** e
	if n % 2 == 0:
		for k in l:
			co = co ^ k
	print(co)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = a
ans = 0
for k in range(29):
	a0 = []
	a1 = []
	a0a = a0.append
	a1a = a1.append
	b0 = []
	b1 = []
	b0a = b0.append
	b1a = b1.append
	for i in a:
		if i & 1 << k:
			a1a(i)
		else:
			a0a(i)
	for i in b:
		if i & 1 << k:
			b1a(i)
		else:
			b0a(i)
	a = a0 + a1
	b = b0 + b1
	mask = (1 << k + 1) - 1
	aa = [i & mask for i in a]
	bb = [i & mask for i in b]
	res = 0
	p1 = 1 << k
	p2 = mask + 1
	p3 = p1 + p2
	j1 = j2 = j3 = 0
	for (jj, ai) in enumerate(reversed(aa)):
		while j1 < n and ai + bb[j1] < p1:
			j1 += 1
		while j2 < n and ai + bb[j2] < p2:
			j2 += 1
		while j3 < n and ai + bb[j3] < p3:
			j3 += 1
		res += max(n, n - jj) - max(j3, n - jj)
		res += max(j2, n - jj) - max(j1, n - jj)
	ans |= (res & 1) << k
print(ans)


import io
import os
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
DEBUG = False

def solveBrute(N, A):
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			ans ^= A[i] + A[j]
	return ans

def solve(N, A):
	B = max(A).bit_length()
	ans = 0
	for k in range(B + 1):
		MOD = 1 << k + 1
		MASK = MOD - 1
		left = []
		right = []
		for x in A:
			if x >> k & 1:
				right.append(x)
			else:
				left.append(x)
		A = left + right
		arr = [x & MASK for x in A]
		if DEBUG:
			assert arr == sorted(arr)
		numPairs = 0
		tLo = 1 << k
		tHi = (1 << k + 1) - 1
		for (targetLo, targetHi) in [(tLo, tHi), (MOD + tLo, MOD + tHi)]:
			lo = N
			hi = N
			for (i, x) in enumerate(arr):
				lo = max(lo, i + 1)
				hi = max(hi, lo)
				while lo - 1 >= i + 1 and arr[lo - 1] >= targetLo - x:
					lo -= 1
				while hi - 1 >= lo and arr[hi - 1] > targetHi - x:
					hi -= 1
				numPairs += hi - lo
				if DEBUG:
					assert lo == bisect_left(arr, targetLo - x, i + 1)
					assert hi == bisect_right(arr, targetHi - x, lo)
					for (j, y) in enumerate(arr):
						cond = i < j and targetLo <= x + y <= targetHi
						if lo <= j < hi:
							assert cond
						else:
							assert not cond
		ans += numPairs % 2 << k
	return ans
if DEBUG:
	import random
	random.seed(0)
	for i in range(100):
		A = [random.randint(1, 1000) for i in range(100)]
		N = len(A)
		ans1 = solveBrute(N, A)
		ans2 = solve(N, A)
		print(A, bin(ans1), bin(ans2))
		assert ans1 == ans2
elif False:
	import random
	random.seed(0)
	A = [random.randint(1, 10 ** 7) for i in range(400000)]
	N = len(A)
	print(solve(N, A))
(N,) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = solve(N, A)
print(ans)


from bisect import bisect_left, bisect_right

def go():
	n = int(input())
	a = list(map(int, input().split()))
	b = max(a).bit_length()
	res = 0
	vals = a
	for i in range(b + 1):
		b2 = 2 << i
		b1 = 1 << i
		a0 = [aa for aa in a if aa & b1 == 0]
		a1 = [aa for aa in a if aa & b1]
		a = a0 + a1
		vals = [aa % b2 for aa in a]
		cnt = 0
		(x1, x2, y1) = (n - 1, n - 1, n - 1)
		for (j, v) in enumerate(vals):
			while x1 > -1 and vals[x1] >= b1 - v:
				x1 -= 1
			while y1 > -1 and vals[y1] > b2 - v - 1:
				y1 -= 1
			(x, y) = (x1 + 1, y1 + 1)
			cnt += y - x
			if x <= j < y:
				cnt -= 1
			while x2 > -1 and vals[x2] >= b2 + b1 - v:
				x2 -= 1
			(x, y) = (x2 + 1, n)
			cnt += y - x
			if x <= j < y:
				cnt -= 1
		res += b1 * (cnt // 2 % 2)
	return res
print(go())


import math
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	temp = []
	ans = 0
	for bit in range(26):
		temp.clear()
		value1 = 2 ** bit
		value2 = 2 ** (bit + 1) - 1
		value3 = 2 ** (bit + 1) + 2 ** bit
		value4 = 2 ** (bit + 2) - 1
		for i in range(n):
			temp.append(a[i] % 2 ** (bit + 1))
		(f1, l1, f2, l2) = [n - 1, n - 1, n - 1, n - 1]
		temp.sort()
		noOfOnes = 0
		for i in range(n):
			while f1 >= 0 and temp[f1] + temp[i] >= value1:
				f1 = f1 - 1
			while l1 >= 0 and temp[l1] + temp[i] > value2:
				l1 = l1 - 1
			while f2 >= 0 and temp[f2] + temp[i] >= value3:
				f2 = f2 - 1
			while l2 >= 0 and temp[l2] + temp[i] > value4:
				l2 = l2 - 1
			noOfOnes = noOfOnes + max(0, l1 - max(i, f1))
			noOfOnes = noOfOnes + max(0, l2 - max(i, f2))
		if noOfOnes % 2 == 1:
			ans = ans + 2 ** bit
	print(ans)
main()


from collections import defaultdict
from queue import deque

def arrinp():
	return [*map(int, input().split(' '))]

def mulinp():
	return map(int, input().split(' '))

def intinp():
	return int(input())

def solution():
	co = 0
	n = int(input())
	l = list(map(int, input().split()))
	for e in range(1, 25):
		po = 2 ** e
		re = sorted([k % po for k in l])
		b = n
		r = 0
		for a in range(n):
			b -= 1
			while re[a] + re[b] >= po and b >= 0:
				b -= 1
			b += 1
			r += n - b - (a >= b)
		r //= 2
		if r % 2:
			co += 2 ** e
	if n % 2 == 0:
		for k in l:
			co = co ^ k
	print(co)
testcases = 1
for _ in range(testcases):
	solution()


from sys import stdin, stdout

def main():
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	ans = 0
	for bit in range(29):
		mask = (1 << bit + 1) - 1
		bit0 = []
		bit1 = []
		for x in arr:
			if x & 1 << bit:
				bit1.append(x)
			else:
				bit0.append(x)
		arr = bit0 + bit1
		temp_arr = [mask & x for x in arr]
		above = 1 << bit + 1
		current = 1 << bit
		abc = above + current
		j1 = j2 = j3 = 0
		res = 0
		for (i, x) in enumerate(reversed(temp_arr)):
			while j1 < n and temp_arr[j1] + x < current:
				j1 += 1
			while j2 < n and temp_arr[j2] + x < above:
				j2 += 1
			while j3 < n and temp_arr[j3] + x < abc:
				j3 += 1
			r1 = n - i - j3 - 1
			if r1 < 0:
				r1 = 0
			r2 = min(n - i - 1, j2) - j1
			if r2 < 0:
				r2 = 0
			res += (r1 + r2) % 2
		if res % 2 == 1:
			ans += current
	stdout.write(str(ans))
main()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = 10 ** 9 + 7
n = int(data())
a = mdata()
ans = 0
for i in range(26):
	M = []
	for j in a:
		M.append(j & (1 << i + 1) - 1)
	M.sort()
	j1 = j2 = j3 = n - 1
	cnt = 0
	for j in range(n):
		while j1 >= 0 and M[j] + M[j1] >= 1 << i:
			j1 -= 1
		while j2 >= 0 and M[j] + M[j2] >= 1 << i + 1:
			j2 -= 1
		while j3 >= 0 and M[j] + M[j3] >= (1 << i) + (1 << i + 1):
			j3 -= 1
		cnt += max(j, j2) - max(j, j1) + n - max(j, j3) - 1
	if cnt % 2 == 1:
		ans += 1 << i
out(ans)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
ANS = 0
for i in range(26):
	B = []
	for a in A:
		B.append(a & (1 << i + 1) - 1)
	B.sort()
	j0 = n - 1
	j1 = n - 1
	j2 = n - 1
	count = 0
	for j in range(n):
		while j0 >= 0 and B[j0] + B[j] >= 1 << i:
			j0 -= 1
		while j1 >= 0 and B[j1] + B[j] > (1 << i + 1) - 1:
			j1 -= 1
		while j2 >= 0 and B[j2] + B[j] >= (1 << i) + (1 << i + 1):
			j2 -= 1
		count += max(j, j1) - max(j, j0) + (n - 1 - max(j, j2))
	if count % 2 == 1:
		ANS += 1 << i
print(ANS)


import math
input_list = lambda : list(map(int, input().split()))

def main():
	n = int(input())
	a = input_list()
	temp = []
	ans = 0
	for bit in range(26):
		temp.clear()
		value1 = 2 ** bit
		value2 = 2 ** (bit + 1) - 1
		value3 = 2 ** (bit + 1) + 2 ** bit
		value4 = 2 ** (bit + 2) - 1
		for i in range(n):
			temp.append(a[i] % 2 ** (bit + 1))
		(f1, l1, f2, l2) = [n - 1, n - 1, n - 1, n - 1]
		temp.sort()
		noOfOnes = 0
		for i in range(n):
			while f1 >= 0 and temp[f1] + temp[i] >= value1:
				f1 = f1 - 1
			while l1 >= 0 and temp[l1] + temp[i] > value2:
				l1 = l1 - 1
			while f2 >= 0 and temp[f2] + temp[i] >= value3:
				f2 = f2 - 1
			while l2 >= 0 and temp[l2] + temp[i] > value4:
				l2 = l2 - 1
			noOfOnes = noOfOnes + max(0, l1 - max(i, f1))
			noOfOnes = noOfOnes + max(0, l2 - max(i, f2))
		if noOfOnes % 2 == 1:
			ans = ans + 2 ** bit
	print(ans)
main()


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
L = max(A).bit_length() + 1
ans = 0
for l in range(L + 1):
	A1 = []
	A2 = []
	for a in A:
		if a & 1 << l:
			A1.append(a)
		else:
			A2.append(a)
	A = A2 + A1
	D = 1 << l + 1
	i1 = N
	i2 = N
	i3 = N
	k = 0
	for (i, a) in enumerate(A):
		while i1 > 0 and a % D + A[i1 - 1] % D >= D // 2:
			i1 -= 1
		while i2 > 0 and a % D + A[i2 - 1] % D >= D:
			i2 -= 1
		while i3 > 0 and a % D + A[i3 - 1] % D >= D // 2 * 3:
			i3 -= 1
		k += i2 - i1 + (N - i3)
		if i1 <= i < i2 or i3 <= i < N:
			k -= 1
	if k % 4 != 0:
		ans += D // 2
print(ans)


import os, sys
from io import BytesIO, IOBase

def cal(arr, mask):
	(su, j) = (0, 0)
	for i in range(len(arr) - 1, -1, -1):
		while j != len(arr) and arr[i] + arr[j] < mask:
			j += 1
		if j >= i:
			return su
		su += i - j
	return su

def cal1(arr, arr1, mask):
	(su, j) = (0, 0)
	for i in range(len(arr) - 1, -1, -1):
		while j != len(arr1) and arr[i] + arr1[j] < mask:
			j += 1
		su += j
	return su

def main():
	n = int(input())
	a = list(map(int, input().split()))
	su = sum((a[i] & 1 for i in range(n))) * sum((not a[i] & 1 for i in range(n)))
	(ans, mask, mask1) = (su & 1, 1, 1)
	for bit in range(1, 25):
		mask <<= 1
		(fir, sec) = ([], [])
		for i in a:
			fir.append(i & mask1) if i & mask else sec.append(i & mask1)
		(fir.sort(), sec.sort())
		su = cal(fir, mask) + cal(sec, mask) + cal1(fir, sec, mask)
		if su & 1:
			ans |= mask
		mask1 |= mask
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()