Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(),dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],(A > x).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  C = 2*B-np.arange(N+1)
  C -= np.min(C) - 1
  M = C.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  prev = C[0]
  for c in C[1:]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,c) # 右端がRとなる(L,R)対
    prev = c
  return cnt <= (total_medians-1)//2

AA = sorted(set(A))
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)
### BUGGY CODE ###

N,M,Q = map(int,input().split())

station = [[0]*N for i in range(N)]

for i in range(M):
    L,R = map(int,input().split())
    station[L-1][R-1] += 1

DP = [[0]*(N) for i in range(N)]

for i in range(N):
    for j in range(N):
        for a in range(i,j+1):
            for b in range(i,j+1):
                DP[i][j] += station[a][b]

for i in range(Q):
    p,q = map(int,input().split())
    print(DP[p-1][q-1])

### FIXED CODE ###

N,M,Q = map(int,input().split())

station = [[0]*(N+1) for i in range(N+1)]

for i in range(M):
    l,r = map(int,input().split())
    station[l][r] += 1

DP = [[0]*(N+1) for i in range(N+1)]

for i in range(N+1):
    for j in range(N):
        DP[i][j+1] = DP[i][j] + station[i][j+1]

for i in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1):
        ans += DP[i][q] - DP[i][p-1]
    print(ans)
### BUGGY CODE ###

import sys
import bisect
 
i_f = sys.stdin
 
n = int(i_f.readline())

Px = []
Py = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    Px.append([x, y, i])
    Py.append([y, x, i])

Px.sort()
Py.sort()

q = int(i_f.readline())

A = []

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(Px, [sx, sy, 0])
    x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
    y_low = bisect.bisect_left(Py, [sy, sx, 0])
    y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
    
    x_width = x_high - x_low
    y_width = y_high - y_low

    a = []
    if x_width < y_width:
        for p in Px[x_low:x_high]:
            if sy <= p[1] <= ty:
                a.append(p[2])
    else:
        for p in Py[y_low:y_high]:
            if sx <= p[1] <= tx:
                a.append(p[2])

    a.sort()
    a.append('')

    print(*a, sep='\n')

### FIXED CODE ###

import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()
### BUGGY CODE ###

import copy
import time
import queue
from collections import deque

def main():
    N, M = map(int, input().split(' '))
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    q = deque([1])
    visited = []
    while len(q)!=0:
        #print(q)
        node = q.popleft()
        visited.append(node)
        #探索
        for nodes in root:
            if nodes[0] == node:
                if not (nodes[1] in visited or nodes[1] in q):
                    signpost[nodes[1]] = node
                    q.append(nodes[1])
            elif nodes[1] == node:
                if not (nodes[0] in visited or nodes[0] in q):
                    signpost[nodes[0]] = node
                    q.append(nodes[0])
    #print(visited)
    print('Yes')
    for i in signpost[2:]:
        print('{:.1g}'.format(i))        

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [None] * (N+1)
    signpost[0] = signpost[1] = 0
    q = deque([1])
    dist = [0 for i in range(N+1)]
    while q:
        node = q.popleft()
        for e in edge[node]:
            if signpost[e] is None:
                dist[e] = dist[node] + 1
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])

for l,r in al:
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)
            
            

### FIXED CODE ###

n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])
### BUGGY CODE ###

import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N = int(input())
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 0
for i in range(N):
    K = max(K, len(repn[i]))
color_set = set([i for i in range(1, K + 1)])
print(K)

q = [(0, K + 1)]
while q:
    u, color = q.pop()
    c_set = deepcopy(color_set)
    c_set.discard(color)
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            c = c_set.pop()
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))

for pair in edge:
    print(color_dict[pair])


### FIXED CODE ###

import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N = int(input())
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 1
q = [(0, None)]
while q:
    u, color = q.pop()
    if color == 1:
        c = 2
    else:
        c = 1
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))
            K = max(K, c)
            c += 1
            if c == color:
                c += 1
                

print(K)
for pair in edge:
    print(color_dict[pair])
### BUGGY CODE ###

from itertools import accumulate

n, k = map(int, input().split())
a = list(map(int, input().split())) + [0]

for _ in range(k):
    l = [0] * (n + 1)
    x = 0
    for i in a[:-1]:
        l[max(0, x - i)] += 1
        l[min(n, x + i + 1)] -= 1
        x += 1
    a = list(accumulate(l))

print(*a[:-1])

### FIXED CODE ###

import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
A = sys.stdin.readline().split()
for i in range(N):
        A[i] = int(A[i])

ans = [0]*N
for i in range(1, N+1):
        ans[i-1] = A.index(i) + 1
print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

ans = [None]*N
for i, order in enumerate(A, 1):
        ans[order-1] = i
print(" ".join(map(str, ans)))
### BUGGY CODE ###

n, w = list(map(int, input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, input().split()))
    weights.append(wi)
    values.append(vi)

dp = [[0 for __ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, w+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] if weights[i-1] <= j else 0)

print(dp[n][w])

### FIXED CODE ###

n, w = list(map(int, raw_input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, raw_input().split()))
    weights.append(wi)
    values.append(vi)

dp = [[0 for __ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, w+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] if weights[i-1] <= j else 0)

print(dp[n][w])
### BUGGY CODE ###

n = int(input())
xlst = list(map(int, input().split()))

for i in range(n):
    x_ = xlst.copy()
    x_.pop(i)
    x_.sort(reverse=True)
    print(x_[n//2-1])


### FIXED CODE ###

n = int(input())
xl = list(map(int, input().split()))
xl_s = sorted(xl)

l = xl_s[n//2-1]
r = xl_s[n//2]

for x in xl:
    if x >= r:
        print(l)
    else:
        print(r)
### BUGGY CODE ###

s=input()

mod=10**9+7

ans=[[0]*13 for _ in range(len(s))]

if s[-1]=="?":
    for i in range(10):
        ans[-1][i%13]+=1
else:
    ans[-1][int(s[-1])%13]+=1

#print(ans)

ten=1
for ii in range(1,len(s)):
    ten=(ten*10)%13

    i=len(s)-ii-1
    
    if s[i]!="?":
        tmp=(int(s[i])*ten)%13
        for j in range(13):
            ans[i][(tmp+j)%13]+=(ans[i+1][j])%mod
    else:
        for k in range(10):
            tmp=(k*ten)%13
            for j in range(13):
                ans[i][(tmp+j)%13]+=(ans[i+1][j])%mod

print(ans[0][5]%mod)





### FIXED CODE ###

s=input()

#i桁以下の数字でmodがjの数
#dp[i][j]=

dp=[[0 for _ in range(13)] for _ in range(len(s))]

MOD=10**9+7

if s[0]!="?":
    dp[0][int(s[0])]=1
else:
    for i in range(10):
        dp[0][i]=1


for i in range(1,len(s)):
    si=s[i]


    if s[i]!="?":
        #数字,300のmodをtempに
        for j in range(13):
            dp[i][(j*10+int(si))%13]+=dp[i-1][j]%MOD
    else:
        for l in range(10):
            for j in range(13):
                dp[i][(j*10+l)%13]+=dp[i-1][j]%MOD
    #print(dp[i],sum(dp[i]))



print(dp[len(s)-1][5]%MOD)
### BUGGY CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    # j桁目のビットが1であるものの数を記憶
    count_zeros = [0 for j in range(L+1)]
    count_ones = [0 for j in range(L+1)]
    for i in range(N):
        for j in range(L):
            count_ones[j] = count_ones[j] + ((A[i] >> j) & 1)
            count_zeros[j] = N - count_ones[j]
    # A[i] と A[j] (i<j) のxorをとる
    modsum = 0
    for j in range(L):
        # MODは一度にとる
        modsum = (count_zeros[j] * count_ones[j] * pow(2, j, MOD) + modsum) % MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


### FIXED CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)


### FIXED CODE ###

#!/usr/bin/env python3

import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for X in range(K+1):
    for Y in range(K+1):
        for Z in range(K+1):
            if X+Y+Z==S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for X in range(K+1):
    for Y in range(K+1):
        if 0<=S-X-Y<=K: #X+Y+Z=S Z=S-X-Y,0<=Z<=K
            count += 1
print(count)
### BUGGY CODE ###

S = input()
Q = int(input())
rev = False
for i in range(Q):
    q = input()
    if q == '1':
        rev = not rev
    else:
        F, C = q.split()[1:]
        if (F == '1' and not rev) or (F == '2' and rev):
            S = C + S
        else:
            S = S + C
if rev:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
rev = False
head = []
tail = []
for i in range(Q):
    q = input()
    if q == '1':
        rev = not rev
    else:
        F, C = q.split()[1:]
        if (F == '1' and not rev) or (F == '2' and rev):
            head.append(C)
        else:
            tail.append(C)

head = ''.join(head)
tail = ''.join(tail)
S = head[::-1] + S + tail
if rev:
    S = S[::-1]
print(S)
### BUGGY CODE ###

def cal_min_cost(num):
    return min([
      abs(hight_list[num] - hight_list[num-diff]) + cost_list[num-diff]
      for diff in range(1,K+1)
      ])

N,K = list(map(int, input().split()))
hight_list = []
cost_list = [0]*K
hight_list = list(map(int, input().split()))
for i in range(K-1):
    hight_list.insert(0,hight_list[0])
for i in range(K, N+K-1):
    cost_list.append(cal_min_cost(i))
print(cost_list[-1])

### FIXED CODE ###

import numpy as np

N,WIDTH = list(map(int, input().split()))

hight_arr = np.array(list(map(int, input().split())))
cost_arr = np.zeros(N,dtype=int)

for i in range(1,N):
    start = max(i-WIDTH,0)
    cost_arr[i] = np.min(np.abs(hight_arr[i] - hight_arr[start:i]) + cost_arr[start:i])
print(cost_arr[-1])
### BUGGY CODE ###

n=int(input())
lista=[0 for i in range(n)]
lista=input().split()
n2=int(input())
listb=[0 for i in range(n2)]
listb=input().split()
cnt=0
for i in range(n2):
    x=0
    for j in range(n):
        if listb[i]==lista[j] and x==0:
            x=1
            cnt+=1
print(cnt)


### FIXED CODE ###

n=int(input())
lista=[int(i) for i in input().split()]
n2=int(input())
listb=[int(i) for i in input().split()]
cnt=0


for i in listb:
    C=int(len(lista)/2)
    D=[0,len(lista)]
    while(1):
        if i<lista[C]:
            for k in D:
                if C>k:
                    d=k
                    break
            D.insert(0,C)
            C=int((C+d)/2)

        elif i>lista[C]:
            for k in D:
                if C<k:
                    d=k
                    break
            D.insert(0,C)
            C=int((C+d)/2)
        else:
            cnt+=1
            break
    
        if C==D[0]:
            break
    
        
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [[0, 0, 0, 0] for _ in range(N+1)]

for i in range(3):
    a, b = A[i], B[i]
    for w in range(N+1):
        if w < a:
            dp[w][i+1] = dp[w][i]
        else:
            dp[w][i+1] = max(dp[w][i], dp[w-a][i+1] + b-a)

M = dp[N][3] + N

dp2 = [[0, 0, 0, 0] for _ in range(M+1)]
for i in range(3):
    a, b = A[i], B[i]
    for w in range(M+1):
        if w < b:
            dp2[w][i+1] = dp2[w][i]
        else:
            dp2[w][i+1] = max(dp2[w][i], dp2[w-b][i+1] + a-b)

print(dp2[M][3]+M)

### FIXED CODE ###

import sys
input = sys.stdin.readline


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

    dp = [0]*((N+1)*4)

    for i in range(3):
        a, b = A[i], B[i]
        for w in range(N+1):
            if w < a:
                dp[w*4+i+1] = dp[w*4+i]
            else:
                dp[w*4+i+1] = max(dp[w*4+i], dp[(w-a)*4+i+1] + b-a)

    M = dp[N*4+3] + N

    dp2 = [0]*((M+1)*4)
    for i in range(3):
        a, b = A[i], B[i]
        for w in range(M+1):
            if w < b:
                dp2[w*4+i+1] = dp2[w*4+i]
            else:
                dp2[w*4+i+1] = max(dp2[w*4+i], dp2[(w-b)*4+i+1] + a-b)

    print(dp2[M*4+3]+M)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    for i in range(n - 1):
        tmp_sum = sum(a[:i+1])
        ans += tmp_sum * a[i+1]
        if ans > m:
            ans = ans % m
    
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from bisect import bisect_right,bisect_left
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A,B = LI(),LI()

# 各桁の xor を考える

ans = 0
mod = 2**29
for i in range(29,0,-1):  # 2**(i-1) の位
    X = [A[j] % mod for j in range(N)]
    Y = [B[j] % mod for j in range(N)]
    Y.sort()
    mod >>= 1
    r = 0
    for j in range(N):
        a = X[j]
        # [2**(i-1)-a,2*2**(i-1)-a),[3*2**(i-1)-a,4*2**(i-1)-a) にある Y の要素の個数を数え上げる
        r += bisect_right(Y,2*mod-a-1) - bisect_left(Y,mod-a)
        r += bisect_right(Y,4*mod-a-1) - bisect_left(Y,3*mod-a)
    if r % 2 == 1:
        ans += mod

print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_right,bisect_left
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A,B = LI(),LI()

# 各桁の xor を考える

ans = 0
mod = 1 << 29
for i in range(29,0,-1):  # 2**(i-1) の位
    X = [a & (mod-1) for a in A]
    Y = [b & (mod-1) for b in B]
    X.sort()
    Y.sort(reverse=True)
    mod >>= 1
    r = 0
    i1,i2,i3 = 0,0,0
    for j in range(N):
        x = X[j]
        # [2**(i-1)-x,2*2**(i-1)-x),[3*2**(i-1)-x,4*2**(i-1)-x) にある Y の要素の個数を数え上げる
        # 尺取り法
        while i1 < N and Y[i1] >= mod-x:
            i1 += 1
        while i2 < N and Y[i2] >= 2*mod-x:
            i2 += 1
        while i3 < N and Y[i3] >= 3*mod-x:
            i3 += 1
        r += i1-i2+i3
    if r % 2 == 1:
        ans += mod

print(ans)
### BUGGY CODE ###

n = range(1,int(input())+1)
a = list(map(int, input().split()))
print(*[a.index(i)+1 for i in n])

### FIXED CODE ###

n = int(input())
x = [0]*n
for i, v in enumerate(map(int, input().split())):
    x[v-1] = i+1
print(*x)
### BUGGY CODE ###

s = list(input())
flag = True
ans = 0
while flag:
    flag = False
    if len(s) <= 1:
        break
    for i in range(len(s)-1):
        if s[i] == '0' and s[i+1] == '1' or s[i] == '1' and s[i+1] == '0':
            del s[i]
            del s[i]
            ans += 2
            flag = True
            break
print(ans)

### FIXED CODE ###

s = input()
print(2*min(s.count('0'),s.count('1')))
### BUGGY CODE ###

N = int(input())
f = 0
count = 0
for j in range(1,N+1):
    count = 0
    for i in range(1,int(j/2)+100000):
        if j%i == 0:
            count +=1
    f = f + (j * count)
print(f)

### FIXED CODE ###

N = int(input())
count = 0
for i in range(1,N+1):
    t = N//i
    count += i * t*(t+1)/2
print(int(count))