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

import sys
import numpy as np
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
a = list(map(float, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)

#dp[i][j][k]は残1がi枚、残2がj枚、残3がk枚のときの残り回数の期待値
#dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp = np.full((N+1, N+1, N+1), -1.0)
dp[0][0][0] = 0.0

def rec(i, j, k):
    if dp[i][j][k] > -1:
        return dp[i][j][k]

    res = 0
    if i > 0:
        res += rec(i - 1, j, k) * i / (i + j + k)
    if j > 0:
        res += rec(i + 1, j - 1, k) * j / (i + j + k)
    if k > 0:
        res += rec(i, j + 1, k - 1) * k / (i + j + k)
    res += N / (i + j + k)
    dp[i][j][k] = res
    return dp[i][j][k]

print(rec(one, two, three))
#print(dp)

### FIXED CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
a = list(map(float, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)

#dp[i][j][k]は残1がi枚、残2がj枚、残3がk枚のときの残り回数の期待値
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0.0

def rec(i, j, k):
    if dp[i][j][k] > -1:
        return dp[i][j][k]

    res = 0
    if i > 0:
        res += rec(i - 1, j, k) * i / (i + j + k)
    if j > 0:
        res += rec(i + 1, j - 1, k) * j / (i + j + k)
    if k > 0:
        res += rec(i, j + 1, k - 1) * k / (i + j + k)
    res += N / (i + j + k)
    dp[i][j][k] = res
    return dp[i][j][k]

for k in range(three + 1):
    for j in range(two + three + 1 - k):
        for i in range(one + two + three + 1 - k - j):
            if i + j + k == 0:
                continue

            res = 0
            if i > 0:
                res += dp[i - 1][j][k] * i / (i + j + k)
            if j > 0:
                res += dp[i + 1][j - 1][k] * j / (i + j + k)
            if k > 0:
                res += dp[i][j + 1][k - 1] * k / (i + j + k)
            res += N / (i + j + k)
            dp[i][j][k] = res

print(dp[one][two][three])
### BUGGY CODE ###

def main():
  n,k,*t=map(int,open(0).read().split())
  *z,=zip(*[iter(t)]*2)
  ok=10**19
  ng=-1
  while ok-ng>1:
    mid=(ok+ng)//2
    if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
    else:ok=mid
  print(ng)
main()

### FIXED CODE ###

n,k,*t=map(int,open(0).read().split())
*z,=zip(*[iter(t)]*2)
ok=10**20
ng=-1
while ok-ng>1:
  mid=(ok+ng)//2
  if sum(max(0,0--(mid-w)//d)for w,d in z)<k:ng=mid
  else:ok=mid
print(ng)
### BUGGY CODE ###

import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
a =[0]+ list(map(int, input().split()))
a_np =np.array(a)
for i in range(N,0,-1):
    a_np[i] =np.sum(a_np[i::i]) %2

print(np.sum(a_np))
a_np =np.delete(a_np,0)
for i,v in enumerate(a_np):
    if v==1:
        print(i+1,end=" ")

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a =[0]+ list(map(int, input().split()))
for i in range(N,0,-1):
    a[i] =sum(a[i::i]) %2
print(sum(a))
del a[0]
for i,v in enumerate(a):
    if v==1:
        print(i+1,end=" ")
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)

#TLEチーンコ
i=0
j=0
b=[]
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif a[i] in b:
        print(-1)
        break
    else:
        b.append(i)
        i=a[i]


### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
'''
#TLEチーンコ
i=0
j=0
b=[]
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif a[i] in b:
        print(-1)
        break
    else:
        b.append(a[i])
        i=a[i]
'''
i=0
j=0
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif j==n:
        print(-1)
        break
    else:
        i=a[i]
### BUGGY CODE ###

#C
N=int(input())
S=input()
even = "#"*N

odd = "."*N
eve_c=0
odd_c=0
ans=[]
for i in range(N):
    ans.append(S[0:i+1].count('#')+S[i+1:].count('.'))
    if S[i]!=even[i]:
        eve_c+=1

    if S[i]!=odd[i]:
        odd_c+=1

ans.append(eve_c)
ans.append(odd_c)
print(min(ans))

### FIXED CODE ###

#https://atcoder.jp/contests/tenka1-2019-beginner/submissions/5063821
from itertools import accumulate
N=int(input())
S=input()
black=[0]*N
white=[0]*N

for i,s in enumerate(S):
    if s=="#":
        black[i]=1
    elif s==".":
        white[i]=1
#累積和を取る
black =[0]+black
black =list(accumulate(black))
white =[0]+white[::-1]
white =list(accumulate(white))[::-1]

ans =[]

for i in range(N+1):
    ans.append(black[i]+white[i])
print(min(ans))
### BUGGY CODE ###

B, C = [[], []]
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
  b, c = map(int, input().split())
  B.append(b)
  C.append(c)

for i in range(len(B)):
  count = 0
  sortA = A
  sortA.sort()
  
  for j in range(len(sortA)):
    if count < B[i]:
      if sortA[j] < C[i]:
        sortA[j] = C[i]
        count = count + 1
      else:
        break
    else:
      break
      
  A = sortA

s = 0  
for _a in A:
  s = s + float(_a)
  
print('%d' % s)

### FIXED CODE ###

from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = defaultdict(int)
for i in range(M):
  b, c = map(int, input().split())
  D[c] += b
  
idx = 0
ans = 0

A.sort()

for c,b in sorted(D.items(), key=lambda x: x[0], reverse=True):
  for _ in range(b):
    if idx >= len(A):
      keep = False
      break
    if A[idx] < c:
      ans += c
      keep = True
    else:
      keep = False
      break
    idx += 1
  if keep:
    continue
  else:
    break
    
for i in range(idx, len(A)):
  ans += A[i]
  
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
value = []
for _ in range(k):
    l, r = map(int, input().split())
    value.append([l, r])
value.sort()
mod = 998244353
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(n - 1):
    for l, r in value:
        for dist in range(l, min(r + 1, n - 1 - i + 1)):
            if i + dist <= n - 1:
                dp[i + dist] = (dp[i] + dp[i + dist]) % mod
print(dp[-1])

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
index_list = []
for _ in range(k):
    l, r = map(int, input().split())
    index_list.append([l, r])

dp = [0 for _ in range(n)]
dpsum = [0 for _ in range(n)]
dp[0] = 1
dpsum[0] = 1
for i in range(1, n):
    for l, r in index_list:
        l_index = max(i - r - 1, -1)
        r_index = i - l
        if r_index >= 0:
            dp[i] += dpsum[r_index]
            if (r_index > l_index) & (l_index >= 0):
                dp[i] -= dpsum[l_index]
    dp[i] = dp[i] % mod
    dpsum[i] = (dp[i] + dpsum[i - 1]) % mod
print(dp[-1])
### BUGGY CODE ###

n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
for i in ans:
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())

DP1 = [0 for _ in range(W+1)]
DP2 = [0 for _ in range(W+1)]

for w, v in A:
    for i in range(w, W+1):
        DP2[i] = max(DP1[i], DP1[i-w] + v)
    DP1 = deepcopy(DP2)

print(DP1[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
q = [(x+1)/2 for x in p]
ans = 0

for i in range(n-k+1):
  x = sum(q[i:i+k])
  if ans < x:
    ans = x
  
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
q = [(x+1)/2 for x in p]
q1 = sum(q[:k])
ans = q1

for i in range(n-k):
  x = q1-q[i] +q[i+k]
  q1 = x
  if ans < x:
    ans = x
  
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
sum=0
while(1):
  for i in range(1,N+1):
    tmp=1/N
    now=i
    while(K>now):
      now*=2
      tmp/=2
    sum+=tmp
print(sum)

### FIXED CODE ###

N,K=map(int,input().split())
sum=0
while(1):
  for i in range(1,N+1):
    tmp=1/N
    now=i
    while(K>now):
      now*=2
      tmp/=2
    sum+=tmp
  break
print(sum)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        if N-r*R-g*G >= 0 and (N-r*R-g*G) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-r*R)//G+1):
        if (N-r*R-g*G) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())
S = []
for i in range(1, len(s) + 1):
    k = 0
    while True:
        count = 0
        if len(s) - k - i < 0:
            break
        a = []
        for j in range(0, i):
            a.append(s[j + k])
        k += 1
        for j in S:
            if j == a:
                count += 1
                break
        if count == 0: S.append(a)

#keylist = []
#for i in range(len(S)):
  #  for j in range(len(S)):
 #       if S[i] == S[j] and i != j and i > j:
#            keylist.append(i)

#for i in keylist:
#    del S[i]
S.sort()
print(''.join(S[K - 1]))


### FIXED CODE ###

s = list(input())
K = int(input())
j = 0
candidate = []
while True:
    if j > 26:
        break
    for i in range(len(s)):
        if s[i] == chr(ord("a") + j):
            for k in range(1, min(6, len(s) - i + 1)):
                candidate.append(s[i:i + k])
    j += 1
i = 1
candidate.sort()
while i < len(candidate):
    if candidate[i] == candidate[i - 1]:
        del candidate[i]
        i -= 1
    i += 1

for i in candidate[K - 1]:
    print(i, end = "")
print()
### BUGGY CODE ###

listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        
money = listA[1][0] + listA[2][0]

for i in range(listA[0][0]):
    for j in range(listA[0][1]):
        if listA[1][i] + listA[2][j] < money:
            money = listA[1][i] + listA[2][j] 

for k in range(listA[0][2]):
    a = listA[k+3][0]
    b = listA[k+3][1]
    wari = listA[1][a-1] + listA[2][b-1] - listA[k+3][2]
    if wari < money:
        money = wari
        
        
print(money)


### FIXED CODE ###

listA=[]

while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        

money = min(listA[1]) + min(listA[2]) 
wari = 100000000

for k in range(listA[0][2]):
    a = listA[k+3][0]
    b = listA[k+3][1]
    if wari > listA[1][a-1] + listA[2][b-1] - listA[k+3][2]:
        wari = listA[1][a-1] + listA[2][b-1] - listA[k+3][2]

if money <= wari:
    print(money)
        
else:
    print(wari)
### BUGGY CODE ###

from sys import stdin

n,k,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [stdin.readline().rstrip() for i in range(q)]
li = [int(v) for v in li]
lin = [k for _ in range(n)]
for i in range(q):
    lin[li[i]-1] += 1
    for s in range(n):
        lin[s] -= 1
for j in range(n):
    if lin[j] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

from sys import stdin

n,k,q = [int(x) for x in stdin.readline().rstrip().split()]
li = []
for _ in range(q):
    li.append(stdin.readline().rstrip())
li = list(map(int, li))
p = k-q
lin = [p for _ in range(n)]
for i in range(q):
    lin[li[i]-1] += 1
for v in range(n):
    if lin[v] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    used = [False] * len(P)
    for index in range(1, len(P)):
        if used[index]:
            continue
        used[index] = True
        graph = [C[index]]
        index = P[index]
        while not used[index]:
            graph.append(C[index])
            used[index] = True
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    p = set(P[1:])
    while p:
        index = p.pop()
        graph = [C[index]]
        index = P[index]
        while index in p:
            graph.append(C[index])
            p.remove(index)
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

def main():
    import fractions
    import sys
    input = sys.stdin.readline
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    mmm=10**9+7
    for i in a[1:]:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

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

n = int(input())
abc = [tuple(map(int, input().split(" "))) for i in range(3)]

abc_list = []
for x in abc:
    d = dict()
    for x_i in x:
        if x_i not in d:
            d[x_i] = 0
        d[x_i] += 1
    abc_list.append(sorted(d.items()))
a, b, c = abc_list

count = 0
for a_i in a:
    for b_i in b:
        for c_i in c:
            if a_i[0] < b_i[0] < c_i[0]:
                count += a_i[1] * b_i[1] * c_i[1]

print(count)

### FIXED CODE ###

import bisect

n = int(input())
abc = [tuple(map(int, input().split(" "))) for i in range(3)]
# n = 100000
# abc = [tuple(range(n)) for i in range(3)]

a, b, c = [sorted(abc_i) for abc_i in abc]

print(sum(bisect.bisect_left(a, b_i) * (n-bisect.bisect(c, b_i)) for b_i in b))
### BUGGY CODE ###

list = input().split(' ')
(A,B,K)=(int(list[0]),int(list[1]),int(list[2]))
for i in range(K):
    if A >= 1:
        A = A-1
    elif B >= 1:
        B = B-1
print(A,B)

### FIXED CODE ###

list = input().split(' ')
(A,B,K)=(int(list[0]),int(list[1]),int(list[2]))
if A >= K:
    A = A - K
elif 1 <= A < K:
    B = B - K + A
    if B < 0:
        B = 0
    A = 0
else:
    A = 0
    B = B - K
    if B < 0:
        B = 0
print(A,B)
### BUGGY CODE ###

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

ab = []
max_a = 0
min_a = 10001
for i in range(N):
    a, b = map(int, input().split())
    if a > max_a:
        max_a = a
    if a < min_a:
        min_a = a
    ab.append([a, b])

# print(max_a, min_a)
inf = float('inf')
dp = [inf for _ in range(H + max_a)]

for a, b in ab:
    for i in range(1, len(dp)):
        # 魔法aだけで体力iを減らすために魔法を使う回数
        times = i // a + (0 if i % a == 0 else 1)
        # 使う魔力
        power = b * times
        if i - a > 0:
            power = min(power, dp[i - a] + b)
        dp[i] = min(dp[i], power)

print(min(dp[H:]))


### FIXED CODE ###

import numpy as np

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

ab = []
for i in range(N):
    a, b = map(int, input().split())
    ab.append([a, b])

ab = np.array(ab)
a_list = ab[:, 0]
b_list = ab[:, 1]
max_a = ab.max()

inf = float('inf')
dp = np.array([inf for _ in range(H + max_a)])
dp[0] = 0

for i in range(1, len(dp)):
    dp[i] = np.amin(dp[np.maximum(i - a_list, 0)] + b_list)

print(int(min(dp[H:])))
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A =list(map(int, input().split()))
B =list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
AB =[]
ABC = []
for i in range(X):
    for j in range(Y):
        ab = A[i] + B[j]
        AB.append(ab)
AB.sort(reverse = True)
m = min(K, X*Y)
for i in range(m):
    for j in range(Z):
        abc = AB[i] + C[j]
        ABC.append(abc)
ABC.sort(reverse = True)
for i in range(K):
    print(ABC[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a =list(map(int, input().split()))
b =list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
abc = []
for i in range(x):
    if (i+1) > k:
        break
    for j in range(y):
        if (i+1)*(j+1) > k:
            break
        for h in range(z):
            if (i+1)*(j+1)*(h+1) >k:
                break
            abc.append(a[i] +b[j] +c[h])
abc.sort(reverse = True)
for i in range(k):
    print(abc[i])
### BUGGY CODE ###

A, B, C, K = map(int, input().split())

if A == B:
    print(0)
else:
    for _ in range(K):
        tmp_A = B + C
        tmp_B = A + C
        C = A + B
        A = tmp_A
        B = tmp_B
        if A - B >= 10 ** 18:
            print(Unfair)
            break
    else:
        print(A-B)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

if K % 2 == 1:
    print(B-A)
elif K % 2 == 0:
    print(A-B)
### BUGGY CODE ###

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

### FIXED CODE ###

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)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import bisect

N = int(input())
s = input().split() 
s = list(s[0])
alf_i = [[] for _ in range(26)]

for i in range(N):
    alf_i[ord(s[i])-97].append(i)


ans=0
for i in range(N):
    x = bisect.bisect_left(alf_i[ord(s[i])-97], i)
    for j in range(x+1,len(alf_i[ord(s[i])-97])):
        y = alf_i[ord(s[i])-97][j]
        cnt=0
        while y+cnt<N and s[i+cnt]==s[y+cnt]:
            if i+cnt==y:
                break
            cnt+=1
        ans = max(cnt,ans)
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

N = int(input())
s = input().split() 
s = list(s[0])

dp = [[0]*(N+1) for _ in range(N+1)]
ans=0
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if s[i]==s[j]:
            dp[i][j]=min(abs(j-i),dp[i+1][j+1]+1)
            ans = max(ans,dp[i][j])
#print(dp)
print(ans)
### BUGGY CODE ###

# coding: utf-8
import itertools
import math

N = int(input())
saidai = int(math.sqrt(N))

def g(x, y, z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

def f(n):
    count = 0
    for (x, y, z) in itertools.product("".join(map(str, (range(1, saidai + 1)))), repeat=3):
        if g(int(x), int(y), int(z)) == n:
            count += 1
    return count

for i in range(1, N+1):
    print(f(i))



### FIXED CODE ###

# coding: utf-8
import itertools
import math

N = int(input())
saidai = int(math.sqrt(N)) + 1

def g(x, y, z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

def f(n):
    result = [0] * (n+1)
    for idx, (x, y, z) in enumerate(itertools.product(range(1, saidai + 1), repeat=3)):
        tmp = g(int(x), int(y), int(z))
        if tmp <= N:
            result[tmp] += 1
    return result

res = f(N)
for i in range(1, N+1):
    print(res[i])
### BUGGY CODE ###

from collections import deque

def bfs(count,adj):
    check = [0]*N
    st = deque()
    push,pop = st.append, st.pop
    push(0)
    check[0] = 1
    while st:
        n = []
        while st:
            n.append(pop())
        for ni in n:
            for i in adj[ni]:
                #print(ni,i,count)
                if check[i] == 0:
                    count[i] += count[ni]
                    check[i] = 1
                    push(i)
    return count

        
N,Q = map(int, input().split())
A = [() for i in range(N)]

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

cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   cnt[p-1] += x

cnt = bfs(cnt,A)

for n in range(N):
    print(cnt[n], end=" ")

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

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

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)