Problem:
 Score : 500 points    Problem Statement You are given two integer sequences, each of length N : a_1, ..., a_N and b_1, ..., b_N .  There are N^2 ways to choose two integers i and j such that 1 \leq i, j \leq N . For each of these N^2 pairs, we will compute a_i + b_j and write it on a sheet of paper.
That is, we will write N^2 integers in total.  Compute the XOR of these N^2 integers.   Definition of XOR  The XOR of integers c_1, c_2, ..., c_m is defined as follows:   Let the XOR be X . In the binary representation of X , the digit in the 2^k 's place ( 0 \leq k ; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k 's place, and 0 if that number is even.   For example, let us compute the XOR of 3 and 5 . The binary representation of 3 is 011 , and the binary representation of 5 is 101 , thus the XOR has the binary representation 110 , that is, the XOR is 6 .

Solution (Python):

"""

https://atcoder.jp/contests/arc092/tasks/arc092_b

桁における1の数の偶奇だけで決まる
1+1 -> 0 (1繰り上がり)
1+0 -> 1
0+0 -> 0
なので、1の位においてはそう

2の位では？繰り上がりがある
繰り上がりも含めて、1がいくつあるかわかればいい
その桁への繰り上がりがあるかは、二分探索でわかるはず

200000*28*log

"""

from sys import stdin
import bisect

N = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
b = list(map(int,stdin.readline().split()))

ans = 0

for i in range(29):

    ndig = 2**i
    now = 0

    for j in a:
        if j & ndig > 0:
            if N % 2 == 1:
                now ^= 1
    for j in b:
        if j & ndig > 0:
            if N % 2 == 1:
                now ^= 1
    
    nb = [j % ndig for j in b]
    nb.sort()
    nb.reverse()
    
    
    for j in a:
        
        na = j % ndig
        l = -1
        r = N

        while r-l != 1:
            m = (l+r)//2
            if nb[m] + na < ndig:
                r = m
            else:
                l = m

        if r % 2 == 1:
            now ^= 1

    ans += now * ndig

print (ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)

Solution (Python):
from bisect import bisect_left
import sys
input = sys.stdin.buffer.readline


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))


ans = 0
for keta in range(0, 29)[::-1]:
    MOD = 1 << (keta + 1)
    T = 1 << keta
    for i in range(n):
        a[i] %= MOD
        b[i] %= MOD
    a.sort(reverse=True)
    b.sort()

    
    
    T1 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < T:
            l += 1
        T1[i] = l

    T2 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < 2 * T:
            l += 1
        T2[i] = l

    T3 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < 3 * T:
            l += 1
        T3[i] = l

    T4 = [0] * n
    l = 0
    for i in range(n):
        while l < n and a[i] + b[l] < 4 * T:
            l += 1
        T4[i] = l

    cnt = 0  
    for i in range(n):
        cnt += (T2[i] - T1[i]) + (T4[i] - T3[i])

    
    if cnt % 2 == 1:
        ans += T

print(ans)

Solution (Python):
from numpy import*
a,b=loadtxt(open(c:=0),'i',skiprows=1)
l=1<<29
while l:u=l;l>>=1;c+=sum(diff(searchsorted(sort(r_[b%u-u,b%u]),([u],[l])-a%u).T))%2*l
print(c)

Solution (Python):
from numpy import*
a,b=loadtxt(open(0),'i',skiprows=1)
c=0
l=1<<29
while l:u=l;l>>=1;c+=sum(diff(searchsorted(sort(r_[b%u-u,b%u]),([u],[l])-a%u).T))%2*l
print(c)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
ln = max(max(a), max(b)).bit_length() + 1
for i in range(ln):
  y = (1 << (i + 1))
  u = [x % y for x in a]
  v = [x % y for x in b]
  y >>= 1
  u.sort(reverse = True)
  v.sort()
  t = 0
  k = 0
  kk = 0
  for x in u:
    while k < N and x + v[k] < y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 2: kk += 1
    t -= N - kk
  k = 0
  kk = 0
  
  for x in u:
    while k < N and x + v[k] < y * 2 + y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 4: kk += 1
    t -= N - kk
    
  
  res ^= t % 2 * y
print(res)

Solution (Python):
from numpy import*
a,b=loadtxt(open(0),'i',skiprows=1)
c=0
l=1<<29
while l:u=l;l>>=1;c+=sum(diff(searchsorted(sort(hstack((b%u-u,b%u))),([u],[l])-a%u).T))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:h=l;l//=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:h=l;l//=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:y=sort(hstack((b%l-l,b%l)));A=l-a%l;l//=2;c+=sum(B(y,A)-B(y,A-l))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=2**29
while l:h,l=l,l>>1;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=loadtxt(open(0),'i',skiprows=1);c=0;l=1<<29
while l:h,l=l,l>>1;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Solution (Python):
import numpy as np
n=int(input())
a=np.array(input().split(),dtype=np.int32)
b=np.array(input().split(),dtype=np.int32)
def f(t,a,b):
  power=1<<t
  mask=(power<<1)-1
  aa=a&mask
  bb=b&mask
  aa.sort()
  bb.sort()
  x1,x2,x3=(np.searchsorted(bb,v-aa).sum() for v in [power,power*2,power*3])
  zero_cnt=x1+(x3-x2)
  return (n*n-zero_cnt)%2
ans=0
for t in range(30):
  x=f(t,a,b)
  if x==1:
    ans+=1<<t
print(ans)

Solution (Python):
import numpy as np
n=int(input())
a=np.array(input().split(),dtype=np.int32)
b=np.array(input().split(),dtype=np.int32)
def f(t,a,b):
  power=1<<t
  mask=(power<<1)-1
  aa=a&mask
  bb=b&mask
  aa.sort()
  bb.sort()
  x1,x2,x3=(np.searchsorted(bb,v-aa).sum() for v in [power,power*2,power*3])
  zero_cnt=x1+(x3-x2)
  return (n-zero_cnt)%2
ans=0
for t in range(30):
  x=f(t,a,b)
  if x==1:
    ans+=1<<t
print(ans)

Solution (Python):
import numpy as np
n=int(input())
a=np.array(input().split(),dtype=np.int32)
b=np.array(input().split(),dtype=np.int32)
def f(t,a,b):
  power=1<<t
  mask=(power<<1)-1
  aa=a&mask
  bb=b&mask
  aa.sort()
  bb.sort()
  x1,x2,x3=(np.searchsorted(bb,v-aa).sum() for v in [power,power*2,power*3])
  zero_cnt=x1+(x3-x2)
  return (n-zero_cnt)%2
ans=0
for t in range(30):
  x=f(t,a,b)
  if x==1:
    ans+=1<<t
print(ans)

Solution (Python):
import sys,bisect
input = sys.stdin.readline


def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))


    res = 0
    p = 0

    for i in range(1,30):
        p += 1<<(i-1)
        A = []
        B = []

        for j in range(n):
            A.append(a[j]&p)
            B.append(b[j]&p)
        A.sort()
        B.sort()

        cnt = 0

        q2 = p+1
        q1 = q2>>1
        q3 = q2<<1

        k1,k2,k3,k4 = 0,0,0,0

        for j in range(n-1,-1,-1):
            while k1 < n and A[j]+B[k1] < q1:
                k1 += 1
            while k2 < n and A[j]+B[k2] < q2:
                k2 += 1
            while k3 < n and A[j]+B[k3] < 3*q1:
                k3 += 1
            while k4 < n and A[j]+B[k4] < q3:
                k4 += 1
            cnt += k4 + k2 - k1 - k3

        
        if cnt%2 != 0:
            res += 1<<(i-1)

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N, = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
mxk = 29
msk = (1<<mxk) - 1
msk2 = (1<<(mxk-1))
r = 0
for i in range(mxk):
    
    for j in range(N):
        Q[j] = Q[j] & msk
        P[j] = P[j] & msk
    msk >>= 1
    P.sort()
    Q.sort()
    j1 = N-1
    j2 = N-1
    b = 0
    ss = N

    for l in range(N):
        if P[l] & msk2:
            ss = l
            break
        k1 = msk2 - (P[l]&msk)
        k2 = k1 + msk2
        while j1 >= 0:
            if Q[j1] < k1:
                break
            j1 -= 1
        while j2 >= 0:
            if Q[j2] < k2:
                break
            j2 -= 1
        b += j2 - j1


    j1 = N-1
    j2 = N-1

    for l in range(ss, N):
        k1 = msk2 - (P[l]&msk)
        k2 = k1 + msk2
        while j1 >= 0:
            if Q[j1] < k1:
                break
            j1 -= 1
        while j2 >= 0:
            if Q[j2] < k2:
                break
            j2 -= 1

        b += j1 + N - j2












    if b%2:
        r += 1<<(mxk-1-i)
    msk2 >>= 1
print(r)

Solution (Python):
from bisect import bisect_left, bisect_right

def solve():
    maxD = 30

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    As.sort()
    Bs.sort()

    ans = 0
    for d in reversed(range(maxD)):
        m1 = 1 << d

        iA = bisect_left(As, m1)
        iB = bisect_left(Bs, m1)

        num1 = N * (N-iA + N-iB)

        As = As[:iA] + [A-m1 for A in As[iA:]]
        Bs = Bs[:iB] + [B-m1 for B in Bs[iB:]]

        As.sort()
        Bs.sort(reverse=True)

        iB = 0
        for A in As:
            while iB < N and A + Bs[iB] >= m1:
                iB += 1
            num1 += iB

        Bs.reverse()

        if num1 % 2:
            ans |= m1

    print(ans)


solve()

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

def xor(L):
    a = 0
    for l in L: a ^= l
    return a

def chk(L1, L2, k):
    L1.sort()
    L2.sort()
    s, j = 0, 0
    for i in range(N)[::-1]:
        while j < N and L1[i] + L2[j] < k:
            j += 1
        s += N - j
    return s % 2 * k

t = (xor(A) ^ xor(B)) * (N % 2)
for i in range(28):
    m = (1 << i+1) - 1
    t ^= chk([a&m for a in A], [b&m for b in B], m + 1)

print(t)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

def xor(L):
    a = 0
    for l in L: a ^= l
    return a

def chk(L1, L2, k):
    L1.sort()
    L2.sort()
    s, j = 0, 0
    for i in range(N)[::-1]:
        while j < N and L1[i] + L2[j] < k:
            j += 1
        s += N - j
    return s % 2 * k

t = (xor(A) ^ xor(B)) * (N % 2)
for i in range(28):
    m = 1 << i+1
    t ^= chk([a%m for a in A], [b%m for b in B], m)

print(t)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))


def f(md, pos):
    res = 0
    fpos = -2
    for av in a:
        while True:
            if pos != -1 and av + b[pos] >= md:
                pos -= 1
            else:
                if fpos == -2:
                    fpos = pos
                res += pos + 1
                break
    return res, fpos


def solve():
    dp = [0] * 31
    for i in range(28, -1, -1):
        md = pow(2, i + 1)
        for j in range(n-1, -1, -1):
            b[j] %= md
            a[j] %= md
        a.sort()
        b.sort()
        pos = n - 1
        res3, pos = f(md // 2 * 3, pos)
        res2, pos = f(md // 2 * 2, pos)
        res1, pos = f(md // 2, pos)
        dp[i] += (n * n - (res1 + res3 - res2)) % 2
    t = 0
    for i in range(31):
        t += pow(2, i) * dp[i]
    print(t)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def sorting(X, l):
    eX = []
    oX = []
    for x in X:
        if x&(1<<l):
            oX.append(x)
        else:
            eX.append(x)
    return eX + oX

ans = 0
for shift in range(30):
    A = sorting(A, shift)
    B = sorting(B, shift)
    div = (1<<(shift+1))
    count = 0
    l1 = N
    r1 = N
    l2 = N
    r2 = N
    for a in A:
        while a%div + B[l1-1]%div >= div//2 and l1 > 0:
            l1 -= 1
        while a%div + B[r1-1]%div >= div and r1 > 0:
            r1 -= 1
        while a%div + B[l2-1]%div >= div//2*3 and l2 > 0:
            l2 -= 1
        while a%div + B[r2-1]%div >= 2*div and r2 > 0:
            r2 -= 1
        count += (r1-l1) + (r2-l2)
    if count%2 == 1:
        ans += (1<<shift)

print(ans)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))


def f(md, pos):
    res = 0
    fpos = -2
    for av in a:
        while True:
            if pos != -1 and av + b[pos] >= md:
                pos -= 1
            else:
                if fpos == -2:
                    fpos = pos
                res += pos + 1
                break
    return res, fpos


def solve():
    dp = [0] * 31
    for i in range(28, -1, -1):
        md = pow(2, i + 1)
        for j in range(n-1, -1, -1):
            b[j] %= md
            a[j] %= md
        a.sort()
        b.sort()
        pos = n - 1
        res3, pos = f(md // 2 * 3, pos)
        res2, pos = f(md // 2 * 2, pos)
        res1, pos = f(md // 2, pos)
        dp[i] += (n * n - (res1 + res3 - res2)) % 2
    t = 0
    for i in range(31):
        t += pow(2, i) * dp[i]
    print(t)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))


def f(md, pos):
    res = 0
    fpos = -2
    for av in a:
        while True:
            if pos != -1 and av + b[pos] >= md:
                pos -= 1
            else:
                if fpos == -2:
                    fpos = pos
                res += pos + 1
                break
    return res, fpos


def solve():
    dp = [0] * 31
    for i in range(28, -1, -1):
        md = pow(2, i + 1)
        for j in range(n-1, -1, -1):
            b[j] %= md
            a[j] %= md
        a.sort()
        b.sort()
        pos = n - 1
        res3, pos = f(md // 2 * 3, pos)
        res2, pos = f(md // 2 * 2, pos)
        res1, pos = f(md // 2, pos)
        dp[i] += (n * n - (res1 + res3 - res2)) % 2
    t = 0
    for i in range(31):
        t += pow(2, i) * dp[i]
    print(t)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import bisect

readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))


def f(md):
    pos = n - 1
    res = 0
    for av in a:
        while True:
            if pos != -1 and av + b[pos] >= md:
                pos -= 1
            else:
                res += pos + 1
                break
    return res


def solve():
    dp = [0] * 31
    for i in range(28, -1, -1):
        md = pow(2, i + 1)
        for j in range(n-1, -1, -1):
            b[j] %= md
            a[j] %= md
        a.sort()
        b.sort()
        res1, res2, res3 = f(md // 2), f(md // 2 * 2), f(md // 2 * 3)
        dp[i] += (n - (res1 + res3 - res2)) % 2
    t = 0
    for i in range(31):
        t += pow(2, i) * (dp[i] % 2)
    print(t)


if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    from bisect import bisect_right as br
    import numpy as np
    n = int(input())
    a = np.array(list(map(int, input().split())))
    b = np.array(list(map(int, input().split())))
    
    
    
    a = np.sort(a)
    b = np.sort(b[::-1])
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    b = pow(2, 28) - b
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        b[temp:] -= j
        b = np.sort(b)
        temp = br(a, j-1)
        k += sum((a & j) // j)
        a[temp:] -= j
        x = (k+br(b, 0))*m % 2
        a = np.sort(a)
        x += np.sum(np.searchsorted(b, a+1))
        ans += (x % 2)*j
    print(ans)


main()

Solution (Python):
def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        temp = br(a, j-1)
        for i in a[:temp]:
            k += (i & j) // j
        for i in range(temp, n):
            k += (a[i] & j) // j
            a[i] -= j
        x = (k+br(b, 0))*m % 2
        a.sort()
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
A.sort()
B.sort()
cnta = [0]*29
cntb = [0]*29
for idx in range(N):
    a, b = A[idx], B[idx]
    for i in range(29):
        if (1<<i) & a:
            cnta[i] = 1 - cnta[i]
        if (1<<i) & b:
            cntb[i] = 1 - cntb[i]

carry = [0]*30
bwa = [0]*N
bwb = [0]*N
for i in range(29):
    m = (1<<(i+1))-1
    bwbc = sorted([b&m for b in B])
    bwac = sorted([m+1 if a&m == 0 else m&(-(a&m)) for a in A])
    r = N
    for idx in range(N-1, -1, -1):
        a = bwac[idx]
        while r and bwbc[r-1] >= a:
            r -= 1
        carry[i+1] += N - r
        
ans = 0
for i in range(29):
    if (carry[i] + (cnta[i]+cntb[i])*N) % 2 == 1:
        ans |= 1<<i
print(ans)

Solution (Python):
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

m = 30
d = []

for i in range(m+1):
    d.append(1<<i)

c = [[] for i in range(m)]
for bi in b:
    for i in range(m):
        c[i].append(bi&(d[i+1]-1))
for i in range(m):
    c[i].sort()

keta = [0]*m


for i in range(m):
    aa = [ai&(d[i+1]-1) for ai in a]
    aa.sort()
    a0 = aa[0]

    i1 = d[i]
    i2 = d[i+1]
    i3 = i2+i1
    b1 = bisect_left(c[i], i1-a0)
    b2 = bisect_left(c[i], i2-a0)
    b3 = bisect_left(c[i], i3-a0)

    for ai in aa:
        
        
        
        while b1-1 >= 0 and c[i][b1-1] >= i1-ai:
            b1 -= 1
        while b2-1 >= 0 and c[i][b2-1] >= i2-ai:
            b2 -= 1
        while b3-1 >= 0 and c[i][b3-1] >= i3-ai:
            b3 -= 1
        keta[i] += b2-b1 + n-b3
    keta[i] %= 2



ans = 0
for i in range(m):
    ans += keta[i]*(1<<i)

print(ans)

Solution (Python):



from bisect import bisect_left

INF = float('inf')

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

def calc_bit(k):
    
    mod = 1 << (k + 1)
    amod = [a & (mod - 1) for a in A]
    bmod = [b & (mod - 1) for b in B]
    amod.sort()
    bmod.sort()
    ret = 0

    
    
    
    b01 = bisect_left(bmod, (1 << k) - amod[0])
    b10 = bisect_left(bmod, (2 << k) - amod[0])
    b11 = bisect_left(bmod, (3 << k) - amod[0])
    for a in range(len(amod)):
        while b01 - 1 >= 0 and bmod[b01 - 1] >= (1 << k) - amod[a]:
            b01 -= 1
        while b10 - 1 >= 0 and bmod[b10 - 1] >= (2 << k) - amod[a]:
            b10 -= 1
        while b11 - 1 >= 0 and bmod[b11 - 1] >= (3 << k) - amod[a]:
            b11 -= 1
        
        ret += b10 - b01
        
        ret += N - b11

    return ret % 2


ans = 0
for i in range(30):
    ans += calc_bit(i) * (1<<i)
print(ans)

Solution (Python):


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    ans = 0
    for k in range(30):
        C = [x & ((1 << (k+1)) - 1) for x in A]
        D = [x & ((1 << (k+1)) - 1) for x in B]
        C.sort()
        D.sort()
        
        
        
        p, q, r = 0, 0, 0
        for i in range(N-1, -1, -1):
            while p < N:
                if C[i] + D[p] >= 1 << k: break
                p += 1
            while q < N:
                if C[i] + D[q] >= 2 << k: break
                q += 1
            while r < N:
                if C[i] + D[r] >= 3 << k: break
                r += 1
            x = ((q - p) + (N - r)) % 2
            
            ans = ans ^ (x << k)
    print(ans)

main()

Solution (Python):

"""
Build answer bit by bit.  For kth bit, let T = 2^k, and consider a, b mod 2T.
Want T <= a+b < 2T or 3T <= a+b
Can use two pointers to find these
"""

def solve(N, A, B):
    ans = 0
    for bit in range(29):
        T = 1 << bit
        A2 = sorted((x % (2*T) for x in A), reverse = True)
        B2 = sorted(x % (2*T) for x in B)
        i1 = i2 = i3 = 0
        
        
        
        
        ending = 0
        for x in A2:
            while i1 < len(B2) and B2[i1] + x < T:
                i1 += 1
            while i2 < len(B2) and B2[i2] + x < 2*T:
                i2 += 1
            while i3 < len(B2) and B2[i3] + x < 3*T:
                i3 += 1
            ending ^= (len(B2) - i3 + i2 - i1) % 2
        ans += ending << bit
    return ans

N = int(raw_input())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
print solve(N, A, B)