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

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

mod = 10**9 + 7

from fractions import gcd

def p_prime(n): 
    prime = [2]
    for i in range(3,n+1):
        flag = 0
        for j in prime:
            if i%j == 0:
                flag = 1
                break
            if i**0.5 < j:
                break
        if flag == 0:
            prime.append(i)
    return prime

def soinsuu(M):
    a = {}
    prime = p_prime(int(M**0.5+1))
    for p in prime:
        count = 0
        while M%p ==0:
            count += 1
            M //= p
        if count > 0:
            a[p] = count
    if M != 1:
        a[M] = 1
    return a

from collections import defaultdict
AA = defaultdict(int)

for i in range(N):
    tmp = soinsuu(A[i])
    for j in tmp:
        AA[j] = max(AA[j],tmp[j])

BB = 1
for k in AA:
    BB *= pow(k,AA[k],mod)
    BB %= mod
    
ans = 0
for i in range(N):
    ans += BB*pow(A[i],mod-2,mod)
    ans %= mod

    
print(ans%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
 
from fractions import gcd
 
def lcm(a,b):
    return a//gcd(a,b)*b

AA = 1
for i in range(N):
    AA = lcm(AA,A[i])
AA %= mod

ans = 0
for i in range(N):
    ans += AA*pow(A[i],mod-2,mod)
    
print(ans%mod)
### BUGGY CODE ###

n = int(input())
a = []
for x in input().split():
    a.append(int(x))

ans = []

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_list(numbers):
    element = gcd(numbers[0], numbers[1])
    if len(numbers)==2:
        return element
    else:
        for i in range(2, len(numbers)):
            element=gcd(element, numbers[i])
        return element

if n == 2:
    print(max(a))
else:
    for i in range(n):
        c = a.copy()
        c.remove(a[i])
        ans.append(gcd_list(c))

    print(max(ans))


### FIXED CODE ###

def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

N=int(input())
A=[int(i) for i in input().split()]
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])
Z=[gcd(X[i],Y[i]) for i in range(N)]
print(max(Z))
### BUGGY CODE ###

N, A = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0 for i in range(N*A+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1


for i in range(N):
    for j in range(N*A+1):
        for k in range(N):
 #i個の整数のうちk個使ってjにする場合の数
            if x[i] > j:
                dp[k][i+1][j] = dp[k][i][j]
            else:
                dp[k+1][i+1][j] = dp[k][i][j - x[i]] + dp[k+1][i][j]

ans = 0
for i in range(1, N + 1):
    ans += dp[i][N][A * i]
print(ans)


### FIXED CODE ###

N, A = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0 for i in range(N*A+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1


for i in range(N):
    for j in range(N*A+1):
        for k in range(N):
 #i個の整数のうちk個使ってjにする場合の数
            if x[i] > j:
                dp[k][i+1][j] = dp[k][i][j]
            else:
                dp[k+1][i+1][j] = dp[k][i][j - x[i]] + dp[k+1][i][j]

ans = 0
for i in range(1, N + 1):
    ans += dp[i][N][A * i]
print(ans)
### BUGGY CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

nCa = cmb(n,a,mod)
nCb = cmb(n,b,mod)
ans = (int(pow(2,n)) - nCa - nCb - 1)%10**9+7

print(ans)

### FIXED CODE ###

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

MOD = 10**9+7

def comb(n,r,MOD):
    x = n+1
    y = min(r,n-r)
    
    numer = 1
    denom = 1
    
    for i in range(1,r+1):
        numer = numer*(x-i)%MOD
        denom = denom*(i)%MOD
    
    return numer * pow(denom,MOD-2,MOD) % MOD

nCa = comb(n,a,MOD)
nCb = comb(n,b,MOD)

ans = pow(2,n,MOD)-1 - nCa - nCb

if ans < 0:
    print((ans+MOD)%MOD)
else:
    print(ans%MOD)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(1,N):
    ans+=i
print(ans)

### FIXED CODE ###

N=int(input())
ans=N*(N-1)//2
print(int(ans))
### BUGGY CODE ###

n,k = map(int,input().split())
A=[*map(int,input().split())]
# print(n,k)
# print(A)
B = []
for i in range(min({18,k,n})):
    # print(i,A)
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = min(n-1, j+d) # 範囲
        # print('j,d,l,r',j,d,l,r)
        for k in range(l,r+1): # [l,r]
            B[k] += 1
    A = B

print(*A, sep=' ')


### FIXED CODE ###

n,k = map(int,input().split())
A=[*map(int,input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = j+d+1 # 範囲
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    # print(B)
    if is_same: break
    A = B
# print(B)
print(*B,sep=' ')
### BUGGY CODE ###

N = int(input())

a = 0
while N > 0:
  a += N % 10
  N //= 10
  a %= 9

if a == 0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

if int(input()) % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import numpy as np
n,k=[int(i) for i in input().split()]
h=[int(input()) for i in range(n)]
h.sort()
sub=[]

for i in range(n-k+1):
  sub.append(np.max(h[i:i+k])-np.min(h[i:i+k]))
print(np.min(sub))  
  
 

### FIXED CODE ###

n,k=[int(i) for i in input().split()]
h=[int(input()) for i in range(n)]
h.sort()
sub=[]

for i in range(n-k+1):
  sub.append(h[i+k-1]-h[i])
print(min(sub))
### BUGGY CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
while True:
    print('Yes' if A[K] > A[0] else 'No')
    A.pop(0)
    if len(A) == K:
        break

### FIXED CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
for i in range (K,N):
    print('Yes' if A[i] > A[i-K] else 'No')
### BUGGY CODE ###

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

a_set = set()
b_set = set()

i = 2
while a!=1:
  if a%i==0:
    while a%i==0: 
      a//=i
    a_set.add(i)
  i+=1

i = 2
while b!=1:
  if b%i==0:
    while b%i==0: 
      b//=i
    b_set.add(i)
  i+=1  
  
print(len(a_set&b_set)+1)

### FIXED CODE ###

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

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

print(len(set(factorize(a))&set(factorize(b)))+1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
T=0
L=10**9+7

for i in range(0,N):
    for j in range(i+1,N):
        x=A[i]*A[j]
        T+=x

ans=T%L
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7 #先に書いておく

s=[0] #sのリスト(累積和)
for i in range(0,N): #累積和を作る
    s.append(s[i]+A[i])

sum=0
for j in range(0,N): #合計をだす
    sum+=A[j]*(s[N]-s[j+1])

ans=sum%MOD #10^9+7で割った余りが答え
print(ans)
### BUGGY CODE ###

from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    r = list()
    result = None
    for i in range(1,clen-2):
        #print("i={}\tL{}, R{}".format(i, l[0:i+1], l[i+1:]))

        # find C0 for each i
        odiff = None
        for c in range(i):
            B = S(0,c)
            C = S(c+1,i)
            diff = abs(B-C)
            if odiff is None:
                odiff = diff
            if odiff < diff:
                break
            odiff = diff
            mb = B
            mc = C

        # find C2 for each i
        odiff = None
        for c in range(i+1,clen-1):
            D = S(i+1, c)
            E = S(c+1, clen-1)
            diff = abs(E-D)
            if odiff is None:
                odiff = diff
            if odiff < diff:
                break
            odiff = diff
            md = D
            me = E

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

### FIXED CODE ###

from itertools import accumulate

def Sdiff(s, m, e):
    # Sdiff(s, m, e) = [A_s, A_s+1 ..., A_m] [A_m+1 .... A_e]
    #    L = cl[m]-cl[s-1], R = cl[e] - cl[m]
    # diff(L,R) = abs(cl[m] - cl[s-1] - cl[e] + cl[m]) = abs(2*cl[m] - cl[s-1] - cl[e])

    x = 0 if s == 0 else cl[s-1]
    return abs(2*cl[m] - x - cl[e])

def partial(start, end, last):
    #print("partial: {}-{} last:{}".format(start,end, last))
    odiff = Sdiff(start, last, end)

    for c in range(last, end):
        diff = Sdiff(start, c, end)
        #print("partial loop: c:{}, diff:{} -> {}".format(c, odiff, diff))
        if odiff < diff:
            return c-1
        odiff = diff
    return c

if __name__ == '__main__':
    # read input
    N = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1, N-2):
        #print("LEFT:RIGHT {}/={}=/{}".format(l[0:i+1], i, l[i+1: N]))
        # LEFT
        c1 = partial(0, i, c1)
        # RIGHT
        c3 = partial(i+1, N-1, c3)

        # evaluate
        mb = cl[c1]
        mc = cl[i] - mb
        md = cl[c3] - cl[i]
        me = cl[N-1] - cl[c3]
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        #print("\t\t{}/{}/{}: [{} {} {} {}]".format(c1, i, c3, mb, mc, md, me))
        #print("\t\tdiff={}".format(diff))
        if diff < result:
            result = diff

    print(result)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    if sum(a)<=k:
        print(0)
    else:
        a.sort()
        f.sort(reverse=True)
        mul=[]
        for i in range(n):
            mul.append([a[i]*f[i],a[i]])
        mul.sort(reverse=True)
        top=0
        for _ in range(k):
            mul[top][0]-=(mul[top][0]//mul[top][1])
            mul[top][1]-=1
            index=1
            if mul[top][0]<mul[top+1][0]:
                mul.append([0,0])
            while mul[top][0]<mul[top+1][0] and mul[top][0]>=mul[-1-index][0]:
                mul[-index]=mul[-1-index]
                index+=1
            if mul[top][0]<mul[top+1][0]:
                mul[-index]=mul[top]
                mul[top]=[0,0]
                top+=1
        print(mul[top][0])

main()

### FIXED CODE ###

def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト atcoder
    # ord(c) chr(2) alphabet <=> number
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    a.sort()
    f.sort(reverse=True)
    ok = 10**12
    ng=-1

    while ok-ng>1:
        mid=(ok+ng)//2
        cnt=0
        for x,y in enumerate(a):
            cnt+=max(0,y-mid//f[x])
        if cnt>k:
            ng=mid
        else:
            ok=mid
    print(ok)
main()
### BUGGY CODE ###

N, L, T = map(int, input().split())
L *= 2
T *= 2

X = [0] * N
W = [0] * N
for i in range(N):
    X[i], W[i] = map(int, input().split())
    X[i] *= 2
    if W[i] == 2:
        W[i] = -1

# print(X, W)
for t in range(T):
    for i in range(N):
        X[i] = (X[i] + W[i]) % L
    for i in range(N):
        if X[i-1] == X[i]:
            W[i-1] *= -1
            W[i] *= -1
    # print(X, W)

for x in X:
    print(x // 2)


### FIXED CODE ###

N, L, T = map(int, input().split())

s = 0
X = [0] * N
for i in range(N):
    x, w = map(int, input().split())
    if w == 1:
        x += T
    else:
        x -= T
    # xが0点を通る回数を足す
    s += x // L
    X[i] = x % L

X.sort()
for i in range(N):
    print(X[(i+s) % N])
### BUGGY CODE ###

import math
X = int(input())

for a in range(1, 3000):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1, 3000):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)
        if an < 0:
            break

        if an == X:
            print(a, b)
            exit()


### FIXED CODE ###

import math
X = int(input())

for a in range(1, 1500):
    a4 = a**4
    a3 = a**3
    a2 = a**2
    for b in range(-1500, 1500):
        an = (a-b)*(a4 + (a3)*b + (a2)*(b**2) + a*(b**3) + b**4)
        if an < 0:
            break

        if an == X:
            print(a, b)
            exit()
### BUGGY CODE ###

a,b,k = map(int,input().split())
for i in range(a,b+1):
    if i < a + k or b - k < i:
        print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())
if b - a + 1  >= 2*k:
    for i in range(a,a+k):
        print(i)
    for j in range(b-k+1,b+1):
        print(j)
else:
    for i in range(a,b+1):
        print(i)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
acc_s=[]
acc_s.append(0)
for i in range(N):
  if i==0:
    acc_s.append(a[i])
  else:
    acc_s.append(a[i]+acc_s[-1])
cnt=0
for i in range(N):
  for j in range(i+1,N+1):
    if acc_s[j]-acc_s[i]==0:
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
N=int(input())
a=list(map(int,input().split()))
acc_s=[]
acc_s.append(0)
dic=defaultdict(int)
dic[0]=1
for i in range(N):
  if i==0:
    acc_s.append(a[i])
    dic[a[i]]+=1
  else:
    v=a[i]+acc_s[-1]
    dic[v]+=1
    acc_s.append(v)
cnt=0
for key in dic.keys():
  v=dic[key]
  cnt+=(v*(v-1)//2)
print(cnt)
### BUGGY CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  while a != pre[a]:
    a = pre[a]
    A.append(a)
  while b != pre[b]:
    b = pre[b]
    B.append(b)
  #print(a,b)
  if a != b:
    pre[b] = a
    for aa in A:
      pre[aa] = a
    for bb in B:
      pre[bb] = a
root = []
cnt = [0 for _ in range(n)]
for i in range(n):
  I = int(i)
  while I != pre[I]:
    I = pre[I]
  root.append(I)
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))
### BUGGY CODE ###

N,X,Y=map(int,input().split())

L=[]
for i in range(1,N):
  for j in range(i+1,N+1):
    l=min(j-i,abs(X-i)+1+abs(j-Y),abs(Y-i)+1+abs(j-X))
    L.append(l)

for i in range(1,N):
  print(L.count(i))

### FIXED CODE ###

N,X,Y=map(int,input().split())

L=[0]*(N)
for i in range(1,N):
  for j in range(i+1,N+1):
    l=min(j-i,abs(X-i)+1+abs(j-Y))
    L[l]+=1

for i in range(1,N):
  print(L[i])
### BUGGY CODE ###

#! /usr/bin/env python3

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

lr = [[0 for i in range(n + 1)] for j in range(n + 1)]
acc = [[0 for i in range(n + 1)] for j in range(n + 1)]

for _ in range(m):
    l, r = map(int, input().split())
    lr[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        acc[i][j] = acc[i][j-1] + lr[i][j]

res = []
for _ in range(qq):
    ans = 0
    p, q = map(int, input().split())
    for i in range(p, q + 1):
        ans += acc[i][q] - acc[i][i - 1]
    res.append(ans)

for row in res:
    print(row)


### FIXED CODE ###

#! /usr/bin/env python3

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

lr = [[0 for i in range(n + 1)] for j in range(n + 1)]
acc = [[0 for i in range(n + 1)] for j in range(n + 1)]

for _ in range(m):
    l, r = map(int, input().split())
    lr[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        acc[i][j] = acc[i][j-1] + lr[i][j]

res = []
for _ in range(qq):
    ans = 0
    p, q = map(int, input().split())
    for i in range(p, q + 1):
        ans += acc[i][q] - acc[i][i - 1]
    res.append(ans)

for row in res:
    print(row)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
n = int(input())
ans = 1
a = (i for i in range(1, n + 1))
for i in a:
    ans *= i
print(ans % MOD)

### FIXED CODE ###

n = int(input())
p = 1
for i in range(1, n + 1):
    p = p * i % 1000000007

print(p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    x,y = map(int, input().split())
    x,y = x-1, y-1
    edges[x].append(y)
    edges[y].append(x)

memo = [[-1]*2 for i in range(n)]
def rec(cur, prev=None):
    white = 1
    black = 1
    for to in edges[cur]:
        if to == prev:
            continue
        w,b = rec(to, cur)
        white *= (w+b)
        white %= mod
        black *= w
        black %= mod
    return white, black

w, b = rec(0)
print((w+b)%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    input = sys.stdin.readline

    mod = 10**9+7
    n = int(input())
    edges = [[] for i in range(n)]
    for i in range(n-1):
        x,y = map(int, input().split())
        x,y = x-1, y-1
        edges[x].append(y)
        edges[y].append(x)

    def rec(cur, prev=None):
        white = 1
        black = 1
        for to in edges[cur]:
            if to == prev:
                continue
            w,b = rec(to, cur)
            white *= (w+b)
            white %= mod
            black *= w
            black %= mod
        return white, black

    w, b = rec(0)
    print((w+b)%mod)

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

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

# check
ans = len([1 for i in range(A, B + 1) if i % C != 0 and i % D != 0])

print(ans)

### FIXED CODE ###

# 判定機にmathがインストールされていないため、
# gcd=最小公倍数、lcm=最少公約数(返り値整数)を実装
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    z = None
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        return z


def lcm(m, n):
    return (m * n) // gcd(m, n)


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

# check
AB = B - (A - 1)

C_cnt = B // C - (A - 1) // C
D_cnt = B // D - (A - 1) // D

lcm_CD = lcm(C, D)
lcm_cnt = B // lcm_CD - (A - 1) // lcm_CD

ans = AB - C_cnt - D_cnt + lcm_cnt

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

#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: str):
    if P == 2 or P ==5:
        answer = 0
        for i in range(N):
            if int(S[i])%P == 0:
                answer += i+1
        print(answer)

        return
    amari = [0]*N

    for i in range(N-1,-1,-1):
        num = int(S[i:N])
        amari[i]=num%P
    from collections import Counter
    counter = Counter(amari)
    answer = 0
    for _,value in counter.items():
        answer += (value*(value-1))//2
    answer += amari.count(0)
    print(answer)  
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: str):
    if P == 2 or P ==5:
        answer = 0
        for i in range(N):
            if int(S[i])%P == 0:
                answer += i+1
        print(answer)
        return

    amari = [0]*N
    amari[N-1] = int(S[N-1])%P
    keta = 1
    for i in range(N-2,-1,-1):
        num = pow(10,keta,P)*int(S[i])
        amari[i]=(amari[i+1]+num)%P
        keta += 1
    from collections import Counter
    counter = Counter(amari)
    answer = 0
    for _,value in counter.items():
        answer += (value*(value-1))//2
    answer += amari.count(0)
    print(answer)  
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

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

n = int(input())
numbers = [int(i) for i in input().split()]
for i in range(0,n):
    count = 0
    while True:
        for i in range(n):
            if numbers[i] % 2 != 0:
                break
            else:
                numbers[i] = int(numbers[i]) / 2
        count += 1
print(count)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            print(ans)
            exit()
    ans += 1
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''

    N, M, K = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    res = 0
    time = 0

    memo_A = [0]
    for i in range(N):
        memo_A.append(As[i]+memo_A[-1])

    memo_B = [0]
    for i in range(M):
        memo_B.append(Bs[i]+memo_B[-1])

    res = 0
    for i, av in enumerate(memo_A):
        if av > K:
            break
        else:
            j = M
            while av + memo_B[j] > K:
                j -= 1
            
            res = max(res,j+i)

    print(res)

if __name__ == "__main__":
    resolve()
            


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    N, M, K = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    Bs = [int(item) for item in input().split()]

    res = 0
    time = 0

    memo_A = [0]
    for i in range(N):
        memo_A.append(As[i]+memo_A[-1])

    memo_B = [0]
    for i in range(M):
        memo_B.append(Bs[i]+memo_B[-1])

    res = 0
    j = M
    for i, av in enumerate(memo_A):
        if av > K:
            break
        else:
            
            while av + memo_B[j] > K:
                j -= 1
            res = max(res,j+i)

    print(res)

if __name__ == "__main__":
    resolve()