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):
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, 2*power, 3*power])
  zero_cnt = x1 + (x3-x2)
  return (N-zero_cnt)%2
  
answer = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		answer += 1<<t

print(answer)

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 sum_count(A,B,x):
  
  
  C = np.searchsorted(B, x-A)
  return C.sum()
 
		
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 = (sum_count(AA,BB,v) for v in [power, 2*power, 3*power])
  zero_cnt = x1 + (x3-x2)
  return (N-zero_cnt)%2
  
answer = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		answer += 1<<t

print(answer)

Solution (Python):
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
T = 1 << 30
for k in range(30, -1, -1):
    cnt = 0

    TT = T << 1
    for i in range(N):
        A[i] %= TT
        B[i] %= TT

    A = sorted(A)
    B = sorted(B)

    d0 = bisect_left(B, T - A[0])
    d1 = bisect_left(B, 2 * T - A[0])
    d2 = bisect_left(B, 3 * T - A[0])
    for i in range(N):
        while d0 - 1 >= 0 and B[d0 - 1] >= T - A[i]:
            d0 -= 1
        while d1 - 1 >= 0 and B[d1 - 1] >= 2 * T - A[i]:
            d1 -= 1
        while d2 - 1 >= 0 and B[d2 - 1] >= 3 * T - A[i]:
            d2 -= 1

        cnt += d1 - d0
        cnt += N - d2

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

    T = T >> 1

print(ans)

Solution (Python):
import bisect
import functools
import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


@debug
def calc_bit(k):
    """
    答えの下から k ビット目を返す
    :param int k:
    :return:
    """
    

    
    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.bisect_left(bmod, (1 << k) - amod[0])
    b10 = bisect.bisect_left(bmod, (2 << k) - amod[0])
    b11 = bisect.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 += len(bmod) - b11

    return ret % 2


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

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
 
def sum_count(A,B,x):
    
    
    p = len(B)-1
    result = 0
    for a in A:
        while p != -1 and a + B[p] >= x:
            p -= 1
        result += p+1
    return result
 
		
def f(t,A,B):
    power = (1<<t)
    AA = [x&(2*power-1) for x in A]
    BB = [x&(2*power-1) for x in B]
    AA.sort()
    BB.sort()
    
    x1,x2,x3 = (sum_count(AA,BB,v) for v in [power, 2*power, 3*power])
    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):
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),'i4',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=split(int32(open(0).read().split()[1:]),2);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=split(int32(open(0).read().split()[1:]),2);c=0;h=l=2**29
while 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;h=l
print(c)

Solution (Python):
from numpy import*;B=searchsorted;a,b=split(int32(open(0).read().split()[1:]),2);c=0
for k in range(29):l=2**k;h=2*l;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,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=2*l;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,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=2*l;y=sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

Solution (Python):
from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)

Solution (Python):
from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    
    
    a = 0
    
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)

Solution (Python):
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
N = read()
A = reads()
B = reads()
 
D = 28
xor = 0
for d in range(D + 1):
  mask = (1 << (d + 1)) - 1 
  AA = sorted(x & mask for x in A)
  BB = sorted(x & mask for x in B)
  count = 0
  itr = [N] * 4
  for a in AA:
    vs = [
      (1 << d) - a,
      (1 << (d + 1)) - a,
      (1 << d) + (1 << (d + 1)) - a,
      (1 << (d + 2)) - a
    ]
    for i in range(4):
      while 0 < itr[i] and vs[i] <= BB[itr[i]-1]:
        itr[i] -= 1
    count += (itr[1] - itr[0]) + (itr[3] - itr[2])
  if count & 1:
    xor |= 1 << d
 
print(xor)

Solution (Python):

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

M = 32
MOD = [(2 << i) for i in range(M+1)]

from bisect import bisect
def make(B):
    S = [None]*M
    s = {}; get = s.get
    for b in B:
        s[b] = get(b, 0) ^ 1
    S[M-1] = sorted(b for b in s if s[b])

    for i in range(M-2, -1, -1):
        t = S[i+1]; l = len(t)
        m = MOD[i]
        mid = bisect(t, m-1)
        def gen(p, q):
            while p < mid and q < l:
                u = t[p]; v = t[q]
                if u+m == v:
                    p += 1; q += 1
                elif u+m < v:
                    yield t[p]; p += 1
                else:
                    yield t[q]-m; q += 1
            while p < mid:
                yield t[p]; p += 1
            while q < l:
                yield t[q]-m; q += 1
        *S[i], = gen(0, mid)
    return S
S = make(A)
T = make(B)

ans = 0
if 0 in S[0]:
    ans ^= 1 in T[0]
if 1 in S[0]:
    ans ^= 0 in T[0]

for i in range(1, M):
    s = S[i]; ls = len(S)
    t = T[i]; lt = len(t)
    m = MOD[i]; p = MOD[i-1]
    P = p+m; Q = 2*m

    if lt:
        c = 0
        f = lt
        while P <= t[f-1]:
            f -= 1

        u = f; v = lt
        for a in s:
            while u > -lt and P <= a + t[u-1] + (u > 0)*m:
                u -= 1
            while v > -lt and Q <= a + t[v-1] + (v > 0)*m:
                v -= 1
            c += (v - u)
        if c & 1:
            ans ^= 1 << i
print(ans)

Solution (Python):

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

M = 32
MOD = [(2 << i) for i in range(M+1)]

from bisect import bisect
def make(B, mode):
    S = [None]*M
    s = {}; get = s.get
    for b in B:
        s[b] = get(b, 0) ^ 1
    S[M-1] = sorted(b for b in s if s[b])

    for i in range(M-2, -1, -1):
        t = S[i+1]; l = len(t)
        m = MOD[i]
        mid = bisect(t, m-1)
        def gen(p, q):
            while p < mid and q < l:
                u = t[p]; v = t[q]
                if u+m == v:
                    p += 1; q += 1
                elif u+m < v:
                    yield t[p]; p += 1
                else:
                    yield t[q]-m; q += 1
            while p < mid:
                yield t[p]; p += 1
            while q < l:
                yield t[q]-m; q += 1
        *S[i], = gen(0, mid)
    if mode:
        for i in range(M):
            m = MOD[i]
            S[i] += list(map(lambda x: x+m, S[i]))
    return S
S = make(A, 0)
T = make(B, 1)

ans = 0
if 0 in S[0]:
    ans ^= 1 in T[0]
if 1 in S[0]:
    ans ^= 0 in T[0]

for i in range(1, M):
    s = S[i]; ls = len(S)
    t = T[i]; lt = len(t)
    m = MOD[i]; p = MOD[i-1]
    P = p+m; Q = 2*m

    if lt:
        c = 0
        f = lt
        while P <= t[f-1]:
            f -= 1

        u = f; v = lt
        for a in s:
            while u > 0 and P <= a + t[u-1]:
                u -= 1
            while v > 0 and Q <= a + t[v-1]:
                v -= 1
            c += (v - u)
        if c & 1:
            ans ^= 1 << i
print(ans)

Solution (Python):

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

M = 32
MOD = [(2 << i) for i in range(M+1)]

from bisect import bisect
def make(B, mode):
    S = [None]*M
    s = {}; get = s.get
    for b in B:
        s[b] = get(b, 0) ^ 1
    S[M-1] = sorted(b for b in s if s[b])

    for i in range(M-2, -1, -1):
        t = S[i+1]; l = len(t)
        m = MOD[i]
        mid = q = bisect(t, m-1)
        p = 0
        if q < l:
            if p < mid:
                def gen(p, q):
                    u = t[p]; v = t[q]
                    while p < mid and q < l:
                        if u+m == v:
                            p += 1; u = t[p] if p < mid else None
                            q += 1; v = t[q] if q < l else None
                        elif u+m < v:
                            yield u
                            p += 1; u = t[p] if p < mid else None
                        else:
                            yield v-m
                            q += 1; v = t[q] if q < l else None
                    while p < mid:
                        yield t[p]; p += 1
                    while q < l:
                        yield t[q]-m; q += 1
                *S[i], = gen(p, q)
            else:
                *S[i], = (u-m for u in t)
        else:
            *S[i], = t
    if mode:
        for i in range(M):
            m = MOD[i]
            S[i] += list(map(lambda x: x+m, S[i]))
    return S
S = make(A, 0)
T = make(B, 1)

ans = 0
if 0 in S[0]:
    ans ^= 1 in T[0]
if 1 in S[0]:
    ans ^= 0 in T[0]

for i in range(1, M):
    s = S[i]; ls = len(S)
    t = T[i]; lt = len(t)
    m = MOD[i]; p = MOD[i-1]
    P = p+m; Q = 2*m

    if lt:
        c = 0
        f = lt
        while P <= t[f-1]:
            f -= 1

        u = f; v = lt
        for a in s:
            while u > 0 and P <= a + t[u-1]:
                u -= 1
            while v > 0 and Q <= a + t[v-1]:
                v -= 1
            c += (v - u)
        if c & 1:
            ans ^= 1 << i
print(ans)