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

from math import gcd
from functools import reduce
# from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

if reduce(gcd,a)!=1:
  print("not coprime")
  exit()

def primes(x):
  ret=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.append(i)
      if x//i!=i:
        ret.append(x//i)
  ret.sort()
  return ret[1:]
      
s=set()
for q in a:
  p=primes(q)
  for j in p:
    if j in s:
      print("setwise coprime")
      exit()
    s.add(j)
print("pairwise coprime")


### FIXED CODE ###

from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
d=defaultdict(int)
for q in a:
  p=primeFactor(q)
  for j in p:
    d[j]+=1

for _,di in d.items():
  if di>=2:
    print("setwise coprime")
    exit()
print("pairwise coprime")
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
p = [0]*n

if k>q:
    for i in range(n):
        print('Yes')
    exit()
else:
    for i in range(n):
        p[i]=a.count(i+1)
        if k+p[i]-q<=0:
            print('No')
        else:
            print('Yes')

### FIXED CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]

p = [k-q]*(n)
for i in a:
    p[i-1] +=1

for i in range(n):
    if p[i]>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
def add(num):
    if len(inf[num]) == 0:
        return 0
    for k in inf[num]:
        inf[k].remove(num)
        point[k] += point[num]
        add(k)
     
add(0)
print(*point)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf') for _ in range(n)]
dp[0] = 0


for i in range(n-1):
  for j in range(1, k+1):
    if i+j <= n-1 and dp[i] + abs(h[i+j]-h[i]) < dp[i+j]:
      dp[i+j] = dp[i] + abs(h[i+j]-h[i])

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf') for _ in range(n)]
dp[0] = 0


for i in range(n-1):
  for j in range(1, k+1):
    if i+j <= n-1 and dp[i] + abs(h[i+j]-h[i]) < dp[i+j]:
      dp[i+j] = dp[i] + abs(h[i+j]-h[i])

print(dp[n-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
money = 1000
kabu = 0
for i in range(N-1):
    if A[i+1] < A[i]:
        while kabu != 0:
            money += A[i]
            kabu -= 1
    else:
        while money >= A[i]:
            money -= A[i]
            kabu += 1
while kabu != 0:
    money += A[-1]
    kabu -= 1
print(money)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
money = 1000
kabu = 0
for i in range(N-1):
    if A[i+1] < A[i]:
        money += A[i] * kabu
        kabu = 0
    else:
        kabu += money//A[i]
        money -= A[i] * (money//A[i])
    #print(kabu,money)
money += A[-1] * kabu


print(money)
### BUGGY CODE ###

n = int(input())
pn = list(map(int, input().split()))
count = 1

for i in range(1,len(pn)):
    if min(pn[:i]) > pn[i]: count += 1
print(count)


### FIXED CODE ###

n = int(input())
pn = list(map(int, input().split()))
count = 1
min = pn[0]

for i in range(1,len(pn)):
    if min > pn[i - 1]: min = pn[i - 1]
    if min > pn[i]: count += 1
print(count)
### BUGGY CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]

dp = [[[False]*((H+W)*80) for _ in range(W)] for _ in range(H)]

dp[0][0][abs(A[0][0]-B[0][0])] = True
for h in range(H-1):
    for w in range(W-1):
        for v in range((H+W)*80):
            v1 = abs(A[h+1][w]-B[h+1][w])
            v2 = abs(A[h][w+1]-B[h][w+1])
            if dp[h][w][v]:
                dp[h+1][w][v1+v] = True
                dp[h+1][w][abs(v1-v)] = True
                dp[h][w+1][v2+v] = True
                dp[h][w+1][abs(v2-v)] = True

v0 = abs(A[H-1][W-1]-B[H-1][W-1])
for v in range((H+W)*80):
    if dp[H-1][W-2][v]:
        dp[H-1][W-1][v0+v] = True
        dp[H-1][W-1][abs(v0-v)] = True
    if dp[H-2][W-1][v]:
        dp[H-1][W-1][v0+v] = True
        dp[H-1][W-1][abs(v0-v)] = True

for v in range((H+W)*80):
    if dp[H-1][W-1][v]:
        ans = v
        break

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = [0] + [int(i) for i in input().split()]

route = [1]
start = 1
duplicate = 0
cnt = 1

while True:
  start = A[start]
  if start in route:
    route.append(start)
    duplicate = start
    break
  else:
  	route.append(start)
  
  if cnt == K:
    print(start)
    exit()
  cnt += 1
  
loop = len(route) - route.index(duplicate) - 1
bias = route.index(duplicate) 

K -= bias
K = K % loop
route = route[route.index(duplicate):-1]

print(route[K])


### FIXED CODE ###

N,K = map(int,input().split())
A = [0] + [int(i) for i in input().split()]

route = [1]
route_set = set()
start = 1
cnt = 0
while True:
  if cnt == K:
    print(route[-1])
    exit()
  elif A[start] in route_set:
    index = route.index(A[start])
    loop = len(route) - index
    break
  else:
    route.append(A[start])
    route_set.add(A[start])
    start = A[start]
    cnt += 1

K -= index
K = K % loop
print(route[index:][K])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
 
for i in range(len(a)):
  b = a.copy()
  del b[i]
  print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a, reverse=True)
for i in range(n):
    if b[0] == b[1]:
        print(b[0])
    else:
        if a[i] == b[0]:
            print(b[1])
        else:
            print(b[0])
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_N = []

for i in list_A:
    list_N.append([i, "A"])

for i in list_B:
    list_N.append([i, "B"])

for i in list_C:
    list_N.append([i, "C"])

k = x + y
cnt = 0
ans = 0
list_N.sort(key=lambda x:x[0], reverse=True)
while True:
    if cnt == k:
        break
    l = list_N.pop(0)

    if l[1] == "A" and x != 0:
        x -= 1
        cnt += 1
        ans += l[0]

    if l[1] == "B" and y != 0:
        y -= 1
        cnt += 1
        ans += l[0]

    if l[1] == "C":
        cnt += 1
        ans += l[0]

print(ans)

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_C = list(map(int, input().split()))
list_A.sort(reverse=True)
list_B.sort(reverse=True)
list_C.sort(reverse=True)

list_N = list_A[:x] + list_B[:y] + list_C[:min(c, x + y)]
list_N.sort(reverse=True)
print(sum(list_N[:x+y]))
### BUGGY CODE ###

from collections import defaultdict

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

dct = defaultdict(int)
for _ in range(N):
  dct[nums.pop()] += 1

for _ in range(Q):
  B, C = map(int,input().split())
  if B in dct:
    if C in dct:
      dct[C] += dct.pop(B)
    else:
      dct[C] = dct.pop(B)

  sum = 0
  for k, v in dct.items():
    sum += k * v
  
  print(sum)


### FIXED CODE ###

from collections import defaultdict

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

res = 0

dct = defaultdict(int)
for _ in range(N):
  n = nums.pop()
  dct[n] += 1
  res += n

for _ in range(Q):
  B, C = map(int,input().split())
  if B in dct:
    n = dct.pop(B)
    res += (C - B) * n
    if C in dct:
      dct[C] += n
    else:
      dct[C] = n
  
  print(res)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
cands = [0]*max(a)

ans = 0
for num in a:
    for i in range(num, max(a)+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
M = max(a)
cands = [0]*M

ans = 0
for num in a:
    if cands[num-1] >= 2:
        continue
    for i in range(num, M+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

h,n = [int(i) for i in input().split()]

l = sorted([[int(i) for i in input().split()] for _ in range(n)],key = lambda x: x[0])

inf = float('inf')
memo = [inf for _ in range(10**5)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        memo[i+x] = min(memo[i+x],memo[i] + y)
print(min(memo[h:]))

### FIXED CODE ###

h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]
 
inf = float('inf')
memo = [inf for _ in range(h+1)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        j = min(i+x, h)
        memo[j] = min(memo[j],memo[i] + y)
print(memo[-1])
### BUGGY CODE ###

import math
a,b,x = map(int,input().split())
print(sum([1 for i in range(a,b+1) if i % x == 0]))
#print(b // x - (a - 1) // x)


### FIXED CODE ###

import math
a,b,x = map(int,input().split())
c = 0
#print(sum([1 for i in range(a,b+1) if i % x == 0]))
print(b // x - (a - 1) // x)
### BUGGY CODE ###

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

while n>0:
  for i in range(a):
    count+=1
    n-=1
    if n==0:
      break
  for i in range(b):
    n-=1
    if n==0:
      break

if a==0:
  print(0)
else:
  print(count)

### FIXED CODE ###

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

ab=a+b
num=n//ab
n-=ab*num

if n>=a:
  ans=a
  
else:
  ans=n
  
print(ans+num*a)
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
        sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)


### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i - 1][j] + sumdp[i][j - 1] +1
#            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %=mod
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)
### BUGGY CODE ###

import numpy as np
N=input()
A=np.array(map(int,raw_input().split()))
B=map(int,raw_input().split())



B2=[[b,i,A[i]] for i,b in enumerate(B)]
B2.sort(reverse=True)
used=[]
gap=0
Ans=0
for b in B2:
    if b[1] not in used and A[b[1]]+gap>=b[0]:
        used.append(b[1])
        if b[0]>A[b[1]]:
            Ans+=1
            gap-=max(0,b[0]-A[b[1]])
    else:
        koho=np.where(A>=b[0])[0]
        koho=list(set(koho)-set(used))
        if len(koho)==0:
            print "-1"
            exit()
        koho_B=np.array([B[k] for k in koho])
        used.append(koho[koho_B.argmin()])
        gap+=A[koho[koho_B.argmin()]]-b[0]
        B[b[1]]=0
        Ans+=1
print Ans

### FIXED CODE ###

N=input()
A=map(int,raw_input().split())
B=map(int,raw_input().split())
need=0
Ans=0

for a,b in zip(A,B):
    if b>a:
        need+=b-a
        Ans+=1
        
index=0

Gap=[a-b for a,b in zip(A,B)]
Gap.sort(reverse=True)

while need>0:
    if Ans+index>=N:
        break
    need-=Gap[index]
    index+=1
    
if need<=0:
    print Ans+index
else:
    print "-1"
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = []
B = []
ans = 0
for _ in range(N):
    i = list(map(int,input().split()))
    A.append(i[0])
    B.append(i[1])
while M != 0:
    ind_ = A.index(min(A))
    if M - B[ind_] > 0:
        M -= B[ind_]
        ans += A[ind_]*B[ind_]
        B[ind_] -= B[ind_]
    else:
        ans += A[ind_]*M
        break
    if B[ind_] <= 0:
        B.pop(ind_)
        A.pop(ind_)
print(ans)

### FIXED CODE ###

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

AB = [list(map(int,input().split())) for i in range(N)]
AB.sort()
ans = 0
for _ in range(N):
    if AB[_][1] >= M:
        ans += AB[_][0]*M
        break
    else:
        ans += AB[_][0]*AB[_][1]
        M -= AB[_][1]
print(ans)
### BUGGY CODE ###

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

for i in range(n):
  if a[n-1-i]%2 == 1:
    b.add(n-i)
    for j in range(1, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1

print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

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

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)
### BUGGY CODE ###

s = input()
N = int(input())
S = []
for _ in range(N):
    S.append(input().split())

order = 1
for res in S:
    if res[0] == "1":
        order = order * - 1
    elif res[1] == "1":
        if order == 1:
            s = res[2]+s
        else:
            s = s+res[2]
    else:
        if order == 1:
            s = s+res[2]
        else:
            s = res[2]+s

if order == -1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = input().split()
sd = deque()
for i in s:
    sd.append(i)
N = int(input())
S = []
order = 1
for _ in range(N):
    res = input().split()
    if res[0] == "1":
        order = order * - 1
    elif res[1] == "1":
        if order == 1:
            sd.appendleft(res[2])
        else:
            sd.append(res[2])
    else:
        if order == 1:
            sd.append(res[2])
        else:
            sd.appendleft(res[2])

sd_str="".join(list(sd))
if order == -1:
    print(sd_str[::-1])
else:
    print(sd_str)
### BUGGY CODE ###

N = int(input())
S = input()

T = ["SS", "SW", "WS", "WW"]

for t in T:
  for i in range(1, N-1):
    if (t[i] == "S" and S[i] == "o") or (t[i] == "W" and S[i] == "x"):
        t += t[i-1]
    else:
        t += "S" if t[i-1] == "W" else "W"
  #print(t)
  
  flag = 1
  if (t[0] == "S" and S[0] == "o") or (t[0] == "W" and S[0] == "x"):
    if t[-1] != t[1]: flag = 0
  else:
    if t[-1] == t[1]: flag = 0
  if (t[-1] == "S" and S[-1] == "o") or (t[-1] == "W" and S[-1] == "x"):
    if t[-2] != t[0]: flag = 0
  else:
    if t[-2] == t[0]: flag = 0
  if flag:
    print(t)
    exit()
print(-1)

### FIXED CODE ###

N = int(input())
S = input()

T = [["S", "S"], ["S", "W"], ["W", "S"], ["W", "W"]]

for t in T:
  for i in range(1, N-1):
    if (t[i] == "S" and S[i] == "o") or (t[i] == "W" and S[i] == "x"):
        t.append(t[i-1])
    else:
        t.append("S" if t[i-1] == "W" else "W")
  #print(t)
  
  flag = 1
  if (t[0] == "S" and S[0] == "o") or (t[0] == "W" and S[0] == "x"):
    if t[-1] != t[1]: flag = 0
  else:
    if t[-1] == t[1]: flag = 0
  if (t[-1] == "S" and S[-1] == "o") or (t[-1] == "W" and S[-1] == "x"):
    if t[-2] != t[0]: flag = 0
  else:
    if t[-2] == t[0]: flag = 0
  if flag:
    print("".join(t))
    exit()
print(-1)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())

a = list(map(int, input().split(' ')))

# 最大公倍数
target_num = lcm(*a)

#b = []
#for i in range(n):
#    b.append(target_num//a[i])
b = [target_num//num for num in a]

print(sum(b) % (10**9+7))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())

a = list(map(int, input().split(' ')))

# 最大公倍数
target_num = lcm(*a)

ans = 0
for i in range(n):
    ans += target_num//a[i]
#b = [target_num//num for num in a]

print(ans % (10**9+7))
### BUGGY CODE ###

#標準入力の受け取り
N = int(input())
A = list(map(int, input().split()))

#Aをbitに表記し直して二次元配列に格納
bit_lis = []
for i in range(N):
    mini_bit_lis = []
    tmp = A[i]
    for j in range(61):
        mini_bit_lis.append(tmp % 2)
        tmp = tmp // 2
    bit_lis.append(mini_bit_lis)

#各桁について値を計算する
ans = 0
bit_1 = 0
mod = 10 ** 9 + 7
for i in range(61):
    for j in range(N):
        if bit_lis[j][i] == 1:
            bit_1 += 1
    if bit_1 == 0:
        continue
    ans += (2 ** i) * bit_1 * (N-bit_1)
    bit_1 = 0
    ans = ans % mod
print(ans)

### FIXED CODE ###

#標準入力の受け取り
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

#Aの各値を二進数にした時の桁ごとに配列にまとめる
bit_lis = [0] * 61
for i in range(61):
    bit_lis[i] = np.count_nonzero(A & 1)
    A >>=1
        
#各桁について値を計算する
ans = 0
bit_1 = 0
mod = 10 ** 9 + 7
for i in range(61):
    bit_1 = bit_lis[i]
    if bit_1 == 0:
        continue
    ans += pow(2, i, mod) * bit_1 * (N-bit_1) 
    ans = ans % mod
print(ans)
### BUGGY CODE ###

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

    total_T_in_A = [0] * (N+1)
    # total_T_in_B = [0] * M
    # total_T_in_B[0] = B[0]
    total_T_in_B = [0] * (M+1)

    for i in range(1, N+1):
        total_T_in_A[i] = total_T_in_A[i-1] + A[i-1]

    for i in range(1, M+1):
        # total_T_in_B[i] = total_T_in_B[i-1] + B[i]
        total_T_in_B[i] = total_T_in_B[i-1] + B[i-1]

    result = 0
    for i in range(N+1):
        # A から i 冊読むときにかかる時間
        i_A_T = total_T_in_A[i]
        
        if K < i_A_T:
            continue

        if K == i_A_T:
            result = max(result, i)
            continue

        rem_T = K - i_A_T

        # total_T_in_B は累積和を格納した、ソート済の配列
        # B_i <= rem_T < B_i+1 となるような B_i を二分探索によって探す

        total_T_in_B_with_INF = total_T_in_B + [10**15]

        first = 0
        last = M + 1
        # total_T_in_B_with_INF[first] <= rem_T < total_T_in_B_with_INF[last] となるような first を二分探索によって探す
        while first < last:
            if abs(last - first) == 1:
                break
            mid = (first + last) // 2
            if rem_T < total_T_in_B_with_INF[mid]:
                last = mid
            else:
                first = mid
        result = max(result, i + first)

    print(result)

main()


### FIXED CODE ###

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

    total_T_in_A = [0] * (N+1)
    total_T_in_A[1] = A[0]
    total_T_in_B = [0] * M
    total_T_in_B[0] = B[0]

    for i in range(2, N+1):
        total_T_in_A[i] = total_T_in_A[i-1] + A[i-1]

    for i in range(1, M):
        total_T_in_B[i] = total_T_in_B[i-1] + B[i]

    result = 0
    for i in range(N+1):
        # A から i 冊読むときにかかる時間
        i_A_T = total_T_in_A[i]
        
        if K < i_A_T:
            continue

        if K == i_A_T:
            result = max(result, i)
            continue

        rem_T = K - i_A_T

        # total_T_in_B は累積和を格納した、ソート済の配列
        # B_i <= rem_T < B_i+1 となるような B_i を二分探索によって探す
        first = total_T_in_B[0]
        last = total_T_in_B[M-1]
        if rem_T < first:
            result = max(result, i)
            continue
        if last <= rem_T:
            result = max(result, i + M)
            continue

        # assume that first <= rem_T <= last
        first_i = 0
        last_i = M - 1
        while first_i < last_i:
            if abs(last_i - first_i) == 1:
                break
            mid_i = (first_i + last_i) // 2
            if rem_T < total_T_in_B[mid_i]:
                last_i = mid_i
            else:
                first_i = mid_i
        result = max(result, i + first_i + 1)

    print(result)

main()