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 p_1, p_2, ..., p_{n}. Lets write down some magic formulas:$q_{i} = p_{i} \oplus(i \operatorname{mod} 1) \oplus(i \operatorname{mod} 2) \oplus \cdots \oplus(i \operatorname{mod} n)$$Q = q_{1} \oplus q_{2} \oplus \ldots \oplus q_{n}$

Here, "mod" means the operation of taking the residue after dividing.

The expression $x \oplus y$ 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 ≤ 10^6). The next line contains n integers: p_1, p_2, ..., p_{n} (0 ≤ p_{i} ≤ 2·10^9).


-----Output-----

The only line of output should contain a single integer — the value of Q.


-----Examples-----
Input
3
1 2 3

Output
3

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
n = int(input())
L = list(map(int, input().split()))
Q = 0
X = [0] * 1000001
for i in range(1, 1000001):
	X[i] = X[i - 1] ^ i
for i in range(1, n + 1):
	Q ^= L[i - 1]
	x = n % i
	y = n // i
	if y % 2 == 1:
		Q ^= X[i - 1]
	Q ^= X[x]
print(Q)


import sys
import math as mt
import bisect
input = sys.stdin.buffer.readline
t = 1
for __ in range(t):
	n = int(input())
	xori = [0] * (n + 1)
	l = list(map(int, input().split()))
	for i in range(1, n + 1):
		xori[i] = xori[i - 1] ^ i
	ans = 0
	for i in range(n):
		if n // (i + 1) % 2 != 0:
			ans ^= l[i] ^ xori[i] ^ xori[n % (i + 1)]
		else:
			ans ^= l[i] ^ xori[n % (i + 1)]
	print(ans)


import functools
import operator
mem = [0]
for i in range(1, 10 ** 6):
	mem.append(mem[-1] ^ i)
n = int(input())
ps = tuple(map(int, str.split(input())))
x = functools.reduce(operator.xor, ps)
for i in range(n):
	(c, m) = divmod(n, i + 1)
	if c & 1:
		x ^= mem[i]
	x ^= mem[m]
print(x)


(n, p) = (int(input()), list(map(int, input().split())))
(s, q) = (0, list(range(n + 1)))
for i in range(1, n + 1):
	q[i] ^= q[i - 1]
	if n // i & 1:
		s ^= q[i - 1]
	s ^= q[n % i]
for i in p:
	s ^= i
print(s)


import bisect
from itertools import accumulate, count
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
from sys import maxsize
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
p = [int(i) for i in input().split()]
s = [0] * n
for i in range(1, n):
	s[i] = s[i - 1] ^ i
q = 0
for i in range(n):
	q = q ^ p[i]
	if n // (i + 1) % 2 == 1:
		q = q ^ s[i]
	q = q ^ s[n % (i + 1)]
print(q)


(n, a) = (int(input()), list(map(int, input().split())))
(x, s) = ([0] * (n + 1), 0)
for i in range(1, n + 1):
	x[i] = i ^ x[i - 1]
	if n // i % 2:
		s ^= x[i - 1]
	s ^= x[n % i]
	s ^= a[i - 1]
print(s)


n = int(input())
p = [int(i) for i in input().split()]
cap_P = 0
for i in p:
	cap_P ^= i
X = [0] * (n + 1)
for i in range(1, n + 1):
	X[i] = X[i - 1] ^ i
for i in range(2, n + 1):
	a = n // i
	r = n % i
	cap_P ^= X[r] ^ (X[i - 1] if a % 2 else 0)
print(cap_P)


def main():
	n = int(input())
	p = list(map(int, input().split()))
	xor = [0 for i in range(n + 1)]
	for i in range(n):
		xor[i + 1] = xor[i] ^ i + 1
	ans = 0
	for i in range(n):
		ans ^= p[i]
	for i in range(n):
		a = n % (2 * (i + 1))
		if a >= i + 1:
			ans ^= xor[i] ^ xor[a - (i + 1)]
		else:
			ans ^= xor[a]
	print(ans)

def __starting_point():
	main()
__starting_point()


from functools import reduce
from itertools import accumulate
from operator import xor
n = int(input())
res = reduce(xor, map(int, input().split()))
pre = [*accumulate(range(n + 1), xor)]
for i in range(1, n + 1):
	res ^= pre[n % i]
	if n // i & 1:
		res ^= pre[i - 1]
print(res)


import sys
inf = float('inf')

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

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

def running_xor(n):
	if n % 4 == 0:
		return n
	elif n % 4 == 1:
		return 1
	elif n % 4 == 2:
		return n + 1
	else:
		return 0
n = int(input())
Arr = get_array()
ans = 0
for i in range(1, n):
	div = n // (i + 1)
	if div & 1:
		ans ^= running_xor(i)
	remainder = n % (i + 1)
	ans ^= running_xor(remainder)
for i in Arr:
	ans ^= i
print(ans)


n = int(input())
ar = list(map(int, input().split()))
dp = [0]
pre = 0
for i in range(1, n + 1):
	pre ^= i
	dp.append(pre)
ans = 0
for i in range(1, n + 1):
	xx = ar[i - 1] ^ dp[i - 1] * (n // i % 2) ^ dp[n % i]
	ans ^= xx
print(ans)


n = int(input())
a = [*map(int, input().split())]
xor_sum = [0] * (n + 1)
ans = 0
for x in a:
	ans ^= x
for i in range(1, n + 1):
	xor_sum[i] = xor_sum[i - 1] ^ i
for i in range(1, n + 1):
	x = n // i
	y = n % i
	if x % 2:
		ans ^= xor_sum[i - 1] ^ xor_sum[y]
	else:
		ans ^= xor_sum[y]
print(ans)


from functools import reduce
from operator import xor
from itertools import accumulate
(n, a) = (int(input()), list(map(int, input().split())))
(arr, mem) = ([0], list(accumulate([i for i in range(n + 1)], lambda x, y: x ^ y)))
for i in range(2, n + 1):
	if n % i == 0:
		arr.append(mem[i - 1] if n // i % 2 else 0)
	else:
		arr.append(mem[n % i] ^ mem[i - 1] if n // i % 2 else mem[n % i])
print(reduce(xor, arr) ^ reduce(xor, a))


n = int(input())
p = map(int, input().split())
f = list(range(n + 1))
for i in range(1, n + 1):
	f[i] ^= f[i - 1]
sum = 0
for i in p:
	sum ^= i
c = []
c.append(0)
for i in range(1, n + 1):
	if n // i & 1:
		c.append(f[i - 1] ^ f[n % i])
	else:
		c.append(f[n % i])
	sum ^= c[i]
print(sum)


def com(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0
n = int(input())
lis = list(map(int, input().split()))
ans = 0
for i in range(1, n + 1):
	a = com(i - 1)
	rem = n % i
	b = com(rem)
	if n // i % 2 == 1:
		ans ^= a ^ b ^ lis[i - 1]
	else:
		ans ^= b ^ lis[i - 1]
print(ans)


def computeXOR(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0
n = int(input())
arr = [int(x) for x in input().split()]
ans = 0
for i in arr:
	ans = ans ^ i
for i in range(1, n + 1):
	if n % i == 0:
		if n // i % 2:
			ans ^= computeXOR(i - 1)
	elif n // i % 2:
		ans ^= computeXOR(i - 1) ^ computeXOR(n % i)
	else:
		ans ^= computeXOR(n % i)
print(ans)


import sys, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def findXOR(n):
	remainder = n % 4
	if remainder == 0:
		return n
	elif remainder == 1:
		return 1
	elif remainder == 2:
		return n + 1
	else:
		return 0

def solution(list1):
	answer = 0
	length = len(list1)
	for i in range(length):
		answer ^= list1[i]
		modded = i + 1
		place = length // modded
		if place % 2 == 0:
			answer ^= findXOR(length % modded)
		else:
			answer ^= findXOR(modded - 1) ^ findXOR(length % modded)
	return answer
n = int(input())
list1 = [int(x) for x in input().split()]
print(solution(list1))


import re
import inspect
from sys import argv, exit

def rstr():
	return input()

def rint():
	return int(input())

def rints(splitchar=' '):
	return [int(i) for i in input().split(splitchar)]

def varnames(obj, namespace=globals()):
	return [name for name in namespace if namespace[name] is obj]

def pvar(var, override=False):
	prnt(varnames(var), var, override=override)

def prnt(*args, override=False):
	if '-v' in argv or override:
		print(*args)

def get_qi(p, i, n, F):
	if n // i % 2 == 1:
		return p ^ F[i - 1] ^ F[n % i]
	else:
		return p ^ F[n % i]

def __starting_point():
	n = rint()
	p = rints()
	F = [0 for i in range(n)]
	for i in range(1, n):
		F[i] = F[i - 1] ^ i
	qs = [get_qi(p, i + 1, n, F) for (i, p) in enumerate(p)]
	Q = None
	for q in qs:
		if Q is None:
			Q = q
		else:
			Q ^= q
	print(Q)
__starting_point()


(t, maxn) = ([0], 1000005)
for i in range(1, maxn):
	t.append(t[-1] ^ i)
(n, res) = (int(input()), 0)
v = [int(i) for i in input().split()]
for i in v:
	res ^= i
for i in range(1, n + 1):
	if n // i % 2 == 1:
		res = res ^ t[i - 1] ^ t[n % i]
	else:
		res ^= t[n % i]
print(res)


def main():
	n = int(input())
	nums = list(map(int, input().split()))
	chunk = []
	base = 0
	for i in range(n + 1):
		base ^= i
		chunk.append(base)
	Q = 0
	for (i, num) in enumerate(nums):
		q = num
		(chunks, res) = divmod(n, i + 1)
		q ^= chunk[res]
		if chunks % 2 == 1:
			q ^= chunk[i]
		Q ^= q
	print(Q)
main()


from functools import reduce
R = lambda : map(int, input().split())
n = int(input())
a = R()
ans = reduce(lambda x, y: x ^ y, a)
f = [0]
for i in range(1, n + 1):
	f.append(f[-1] ^ i)
for i in range(1, n + 1):
	if n // i % 2:
		ans ^= f[i - 1]
	ans ^= f[n % i]
print(ans)


import sys
from math import gcd, sqrt, ceil
from collections import defaultdict, Counter, deque
import math
import os
import sys
from io import BytesIO, IOBase
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')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)
n = int(input())
l = list(map(int, input().split()))
pre = [0]
for i in range(1, n + 10):
	pre.append(pre[-1] ^ i)
ans = 0
for i in range(n):
	ans ^= l[i]
for i in range(2, n + 1):
	z = n // i
	if z % 2 == 0:
		ans ^= pre[n % i]
	else:
		ans ^= pre[n % i] ^ pre[i - 1]
print(ans)


n = int(input())
p = [int(i) for i in input().split()]
xor = [0]
for i in range(1, n + 1):
	xor.append(i ^ xor[i - 1])
total = 0
for i in range(2, n + 1):
	if n % (2 * i) > i:
		total = total ^ xor[i - 1] ^ xor[n % i]
	elif n % (2 * i) == i:
		total = total ^ xor[i - 1]
	else:
		total = total ^ xor[n % (2 * i)]
for i in range(n):
	total = total ^ p[i]
print(total)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
(n,) = I()
l = [0] + I()
ans = 0
xor = [0] * (n + 1)
for i in range(1, n + 1):
	xor[i] = xor[i - 1] ^ i
for i in range(1, n + 1):
	ans ^= l[i]
	if n // i % 2:
		ans ^= xor[i - 1]
	ans ^= xor[n % i]
print(ans)


n = int(input())
a = list(map(int, input().split()))
xor = [0, 1]
for i in range(2, n + 1):
	xor.append(i ^ xor[-1])
ans = 0
for i in range(n):
	ans ^= a[i]
for i in range(1, 1 + n):
	ans ^= xor[n % i]
	if n // i % 2:
		ans ^= xor[i - 1]
print(ans)


n = int(input())
arr = list(map(int, input().split()))
prefix_xor = [0]
for i in range(1, n + 1):
	prefix_xor.append(prefix_xor[-1] ^ i)
ans = 0
for i in range(n):
	ans ^= arr[i] ^ prefix_xor[n % (i + 1)]
	if n // (i + 1) & 1:
		ans ^= prefix_xor[i]
print(ans)


n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	dp[i] = dp[i - 1] ^ i
ans = 0
for i in a:
	ans = ans ^ i
for i in range(2, n + 1):
	x = n // i
	if x & 1:
		ans = ans ^ dp[i - 1]
	rem = n % i
	ans = ans ^ dp[rem]
print(ans)


from sys import stdin, stdout
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
val1 = 0
for i in arr:
	val1 ^= i
store = [0] * (n + 1)
for i in range(1, n + 1):
	c = n // i
	store[0] += c
	store[i] -= c
	r = n % i
	if r >= 1:
		store[1] += 1
		if r + 1 <= n:
			store[r + 1] -= 1
store[0] %= 2
for i in range(1, len(store)):
	store[i] += store[i - 1]
	store[i] %= 2
for i in range(len(store)):
	if store[i] != 0:
		val1 ^= i
print(val1)


n = int(input())
p = list(map(int, input().split()))
f = [0]
for i in range(1, n + 1):
	f.append(f[i - 1] ^ i)
res = 0
for i in range(1, n + 1):
	res = res ^ p[i - 1] ^ f[i - 1] * (n // i % 2) ^ f[n % i]
print(res)


from sys import stdin

def main():
	n = int(stdin.readline())
	ar = list(map(int, stdin.readline().split()))
	f = [0] * (n + 1)
	for i in range(1, n + 1):
		f[i] = f[i - 1] ^ i
	ans = 0
	for i in range(1, n + 1):
		if n // i % 2 == 0:
			ans = ans ^ ar[i - 1] ^ f[n % i]
		else:
			ans = ans ^ ar[i - 1] ^ f[i - 1] ^ f[n % i]
	print(ans)
main()


from sys import stdin, stdout

def fin():
	return stdin.readline()

def fout(x):
	stdout.write(str(x) + '\n')
(n, arr, ans) = (int(fin()), list(map(int, fin().split())), 0)
for i in arr:
	ans ^= i
(pre_xor, post_xor, now) = ([0 for i in range(n + 1)], [0 for i in range(n + 1)], 0)
for i in range(0, n + 1):
	now ^= i
	pre_xor[i] = now
now = 0
for i in range(n, -1, -1):
	now ^= i
	post_xor[i] = now
for i in range(1, n + 1):
	if n // i % 2 == 0:
		ans ^= pre_xor[n % i]
	else:
		ans ^= pre_xor[i - 1] ^ pre_xor[n % i]
fout(ans)


n = int(input())
p = [int(x) for x in input().split()]
d = [0 for i in range(n + 1)]
for i in range(2, n + 1):
	d[i] -= n // i
	d[n % i + 1] -= 1
	d[0] += n // i + 1
sum = 0
a = []
for i in d:
	sum += i
	a.append(sum)
ans = 0
for i in p:
	ans ^= i
for i in range(1, len(a)):
	if a[i] % 2 == 1:
		ans ^= i
print(ans)


import bisect
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	(n, p, s) = (ii(), lmii(), 0)
	x = [0] * (n + 1)
	for i in range(1, n + 1):
		x[i] = x[i - 1] ^ i
	for i in range(1, n + 1):
		s ^= x[n % i] ^ n // i % 2 * x[i - 1] ^ p[i - 1]
	print(s)
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()


n = int(input())
a = [int(x) for x in input().split()]

def fun(n):
	res = 0
	if n % 4 == 0:
		res = n
	elif n % 4 == 1:
		res = 1
	elif n % 4 == 2:
		res = n + 1
	else:
		res = 0
	return res
ans = 0
for i in range(1, n + 1):
	val = 0
	k = n // i
	if k % 2:
		val = fun(i - 1)
	val = val ^ fun(n % i)
	ans ^= val
for i in range(n):
	ans = ans ^ a[i]
print(ans)


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def findXOR(n):
	rem = n % 4
	if rem == 0:
		return n
	elif rem == 1:
		return 1
	elif rem == 2:
		return n + 1
	else:
		return 0

def solution(li):
	ans = 0
	terms = len(li)
	for i in range(len(li)):
		ans ^= li[i]
		modded = i + 1
		place = terms // modded
		if place % 2 == 0:
			ans ^= findXOR(terms % modded)
		else:
			ans ^= findXOR(modded - 1) ^ findXOR(terms % modded)
	return ans

def input_test():
	n = int(input())
	li = list(map(int, input().strip().split(' ')))
	out = solution(li)
	print(out)

def test():
	pass
input_test()


import sys
input = sys.stdin.readline
n = int(input())
ar = list(map(int, input().split()))
dp = [0]
pre = 0
for i in range(1, n + 1):
	pre ^= i
	dp.append(pre)
ans = 0
for i in range(1, n + 1):
	xx = ar[i - 1] ^ dp[i - 1] * (n // i % 2) ^ dp[n % i]
	ans ^= xx
print(ans)


n = int(input())
arr = list(map(int, input().split()))
pre_fix_xor = []
pre_fix_xor.append(0)
for j in range(1, n):
	pre_fix_xor.append(pre_fix_xor[j - 1] ^ j)
ans = 0
for i in range(n):
	ans ^= arr[i]
	if n // (i + 1) % 2 == 0:
		valu = n % (i + 1)
		ans ^= pre_fix_xor[valu]
	else:
		valu = n % (i + 1)
		ans ^= pre_fix_xor[i] ^ pre_fix_xor[valu]
print(ans)


n = int(input())
p = [0] + list(map(int, input().split()))
f = [0] * (n + 1)
for i in range(1, n + 1):
	if i == 1:
		f[i] = i
	else:
		f[i] = f[i - 1] ^ i
c = []
for i in range(1, n + 1):
	if n // i % 2 == 1:
		c.append(p[i] ^ f[i - 1] ^ f[n % i])
	else:
		c.append(p[i] ^ f[n % i])
q = c[0]
for i in range(1, len(c)):
	q = q ^ c[i]
print(q)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))

def fn(x):
	rem = x % 4
	if rem == 0:
		return x
	if rem == 1:
		return 1
	if rem == 2:
		return 1 ^ x
	if rem == 3:
		return 0
for _ in range(1):
	n = nmbr()
	a = lst()
	xor = 0
	for i in range(n):
		xor ^= a[i]
		q = n // (i + 1)
		r = n % (i + 1)
		if q & 1:
			xor ^= fn(i) ^ fn(r)
		else:
			xor ^= fn(r)
	print(xor)


import sys

def solve(n, p):
	tab = [0 for _ in range(n)]
	for i in range(1, n):
		tab[i] = tab[i - 1] ^ i
	columns = []
	for i in range(1, n + 1):
		cycles = n // i
		rem = n % i
		if cycles % 2 == 0:
			columns.append(tab[rem])
		else:
			columns.append(tab[i - 1] ^ tab[rem])
	for i in range(1, len(columns)):
		columns[i] = columns[i - 1] ^ columns[i]
	for i in range(1, len(p)):
		p[i] = p[i - 1] ^ p[i]
	return p[-1] ^ columns[-1]

def readinput():
	n = int(sys.stdin.readline().rstrip())
	p = list(map(int, sys.stdin.readline().rstrip().split(' ')))
	print(solve(n, p))
readinput()


(n, p, l, k, q) = (int(input()), list(map(int, input().split())), [], 0, 0)
for i in range(n):
	k ^= i
	l += [k]
for i in range(n):
	r = i + 1
	q ^= p[i] ^ l[i] * (n // r % 2) ^ l[n % r]
print(q)


n = int(input())
a = list(map(int, input().strip().split(' ')))
d = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
	d[i] ^= i ^ d[i - 1]
k = []
for i in range(n):
	if n // (i + 1) % 2:
		k.append(a[i] ^ d[i] ^ d[n % (i + 1)])
	else:
		k.append(a[i] ^ d[n % (i + 1)])
ans = 0
for j in k:
	ans ^= j
print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def XOR_n(n):
	xor = 0
	if n % 4 == 0:
		xor = n
	elif n % 4 == 1:
		xor = 1
	elif n % 4 == 2:
		xor = n + 1
	else:
		xor = 0
	return xor
n = Int()
p = array()
ans = 0
for i in p:
	ans ^= i
for i in range(1, n + 1):
	xor = 0
	k = n // i
	if k % 2:
		xor = XOR_n(i - 1)
	xor ^= XOR_n(n % i)
	ans ^= xor
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
inp = sys.stdin.buffer.readline

def I():
	return list(map(int, inp().split()))

def xor(n):
	if n % 4 == 1:
		return 1
	elif n % 4 == 2:
		return n + 1
	elif n % 4 == 3:
		return 0
	else:
		return n
(n,) = I()
a = I()
ans = 0
for i in range(n):
	ans ^= xor(i) * (n // (i + 1) % 2 != 0) ^ xor(n % (i + 1)) ^ a[i]
print(ans)


n = int(input())
numbers = map(int, input().split())
c = []
base = 0
for i in range(n + 1):
	base ^= i
	c.append(base)
Q = 0
for (j, num) in enumerate(numbers):
	q = num
	(z, res) = divmod(n, j + 1)
	q ^= c[res]
	if z % 2 == 1:
		q ^= c[j]
	Q ^= q
print(Q)


import sys
from math import *
from fractions import gcd
readints = lambda : list(map(int, input().strip('\n').split()))
n = int(input())
a = list(readints())
P = 0
for p in a:
	P = P ^ p
maxn = 10 ** 6 + 5
prefix = [0] * maxn
for i in range(1, maxn):
	prefix[i] = prefix[i - 1] ^ i
cur = 0
for k in range(1, n + 1):
	base = n // k
	if base % 2 == 1:
		cur = cur ^ prefix[k - 1]
	cur = cur ^ prefix[n % k]
Q = cur ^ P
print(Q)


def getXorSuffix(i, n, xor):
	res = 0 if n // (i + 1) % 2 == 0 else xor[i]
	return res ^ xor[n % (i + 1)]
n = int(input())
p = [int(x) for x in input().split()]
xor = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	xor[i] = i ^ xor[i - 1]
ans = 0
for i in range(len(p)):
	ans ^= p[i] ^ getXorSuffix(i, n, xor)
print(ans)


n = int(input())
p = [int(i) for i in input().split()]
s = [0] * n
for i in range(1, n):
	s[i] = s[i - 1] ^ i
q = 0
for i in range(n):
	q = q ^ p[i]
	if n // (i + 1) % 2 == 1:
		q = q ^ s[i]
	q = q ^ s[n % (i + 1)]
print(q)


n = int(input())
p = list(map(int, input().split()))
cx = [i for i in range(n + 1)]
for i in range(1, n + 1):
	cx[i] = cx[i - 1] ^ cx[i]
x = p[0]
for i in range(1, n):
	x ^= p[i]
for i in range(1, n + 1):
	m = n % i
	rep = n // i
	if rep % 2 == 0:
		x ^= cx[m]
	else:
		x ^= cx[i - 1] ^ cx[m]
print(x)


import sys
import string
import math
import heapq
from collections import defaultdict
from functools import lru_cache
from collections import Counter
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

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

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def main():
	line()
	arr = lmi(line())
	n = len(arr)
	curr_xor = [1]
	ans = 0
	for i in range(2, n + 1):
		(times, rem) = (n // i, n % i)
		if times % 2 != 0:
			ans ^= curr_xor[-1]
		if rem != 0:
			ans ^= curr_xor[rem - 1]
		curr_xor.append(i ^ curr_xor[-1])
	for n in arr:
		ans ^= n
	print(ans)
main()