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: interview

Starter code:

Solutions:
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)


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=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)


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)

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)


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)

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()


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 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: # even
        return p ^ F[i-1] ^ F[n % i]
    else:
        return p ^ F[n % i]

def __starting_point():
    n = rint()
    p = rints()

    # Pre-populate F as the cumulative xor of i
    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()

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 = 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)


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)


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,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)



# Made By Mostafa_Khaled


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 sys
from math import *
from fractions import gcd
readints=lambda:list(map(int, input().strip('\n').split()))

n=int(input())
a=list(readints())


# for k in range(1,9):
#     buf=''
#     for i in range(1,9):
#         buf+=str(i%k)+' '
#     print(buf)

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)
    


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)


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)

'''input
3
1 2 3
'''

from sys import stdin, stdout


# main starts
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)


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()

import sys

inf = float("inf")
# sys.setrecursionlimit(10000000)

# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
# mod, MOD = 1000000007, 998244353
# words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'quarter',16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',25:'twenty five',26:'twenty six',27:'twenty seven',28:'twenty eight',29:'twenty nine',30:'half'}
# vow=['a','e','i','o','u']
# dx,dy=[0,1,0,-1],[1,0,-1,0]

# import random
# from collections import deque, Counter, OrderedDict,defaultdict
# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pi,gcd
# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right

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)
# print(ans)
for i in Arr:
    ans ^= i
print(ans)


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)            



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))


if n > 1:
    if n % 2:
        arr.append(0 if (n // 2) % 2 else 1)
    else:
        arr.append(0 if ((n - 1) // 2) % 2 else 1)

for i in range(3, 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(arr)
print(reduce(xor, arr) ^ reduce(xor, a))