Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
import re
import copy
import sys
import numpy as np

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

for i in range(n):
    c += min(a[i],b[i])
    if a[i] < b[i]:
        a[i+1] -= b[i]-a[i]
        c += b[i]-a[i]

print(c)

Fixed submission:
import math
import re
import copy
import sys

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

for i in range(n):
    c += min(a[i],b[i])
    if a[i] < b[i]:
        c += min(a[i+1],b[i]-a[i])
        a[i+1] -= min(a[i+1],b[i]-a[i])

print(c)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import copy
def py():
    print("Yes")
def pn():
    print("No")
def iin():
    x = int(input())
    return x

neko = 0
nuko = 10

a = []
n = iin()
for i in range(n):
    a.append(iin())
for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    print(max(b))

Fixed submission:
import math
import copy
def py():
    print("Yes")
def pn():
    print("No")
def iin():
    x = int(input())
    return x

neko = 0
nya = 0
nuko = 0

a = []
n = iin()
for i in range(n):
    a.append(iin())
    if neko < a[i]:
        neko = a[i]
b = copy.copy(a)
a.remove(neko)
nya = max(a)
for i in range(n):
    if b[i] == neko:
        print(nya)
    else:
        print(neko)
Buggy python submission (verdict: Runtime Error):
import  sympy
n = int(input())
a = list(map(int,input().split()))
d = {}
for i in [0,1]:
    for j in sympy.divisors(a[i]):
        d[j] = 2
key = list(d.keys())
for i in range(n):
    c = key[:]
    b = sympy.divisors(a[i])
    for j in c:
        if not(j in b):
            d[j] -= 1
            if d[j] == 0:
                key.remove(j)
key = sorted(key,reverse = True)
print(key[0])


Fixed submission:
import math
n = int(input())
a = list(map(int,input().split()))
r ,l = [0] * (n),[0] * (n)
l[0] = 0
r[n-1] = 0
for i in range(1,n):
    l[i] = math.gcd(l[i-1],a[i-1])
    r[n-i-1] = math.gcd(r[n-i],a[n-i])
m = [0] * n
for i in range(n):
    m[i] = math.gcd(l[i],r[i])
print(max(m))

Buggy python submission (verdict: Runtime Error):
import  sympy
n = int(input())
a = list(map(int,input().split()))
d = {}
for i in [0,1]:
    for j in sympy.divisors(a[i]):
        d[j] = 2
key = list(d.keys())
for i in range(n):
    c = key[:]
    b = sympy.divisors(a[i])
    for j in c:
        if not(j in b):
            d[j] -= 1
            if d[j] == 0:
                key.remove(j)
key = sorted(key,reverse = True)
print(key[0])


Fixed submission:
import math
n = int(input())
a = list(map(int,input().split()))
r ,l = [0] * (n),[0] * (n)
l[0] = 0
r[n-1] = 0
for i in range(1,n):
    l[i] = math.gcd(l[i-1],a[i-1])
    r[n-i-1] = math.gcd(r[n-i],a[n-i])
m = [0] * n
for i in range(n):
    m[i] = math.gcd(l[i],r[i])
print(max(m))
Buggy python submission (verdict: Runtime Error):
n = input()
for i in range(3):
    if n[i] == '9':
        n[i] = '1'
    else:
        n[i] = '9'
print(int(n))


Fixed submission:
n = input()
ans = ''
for i in range(3):
    if n[i] == '9':
        ans += '1'
    else:
        ans +=  '9'
print(int(ans))
Buggy python submission (verdict: Runtime Error):
import math
import re
import copy
import sys

a,b,k = map(int,input().split())
l = list(range(a,b+1))
if len(l) < k:
    k = len(l)
for i in l[:k]:
    print(i)
l = l[k:len(l)]
le = len(l)
k = le-k
if k < 0:
    k = 0
for i in l[k:le]:
    print(i)

Fixed submission:
import math
import re
import copy
import sys

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

for i in range(a,min(a+k,b+1)):
    print(i)

for j in range(max(b-k+1,i+1),b+1,1):
    print(j)

Buggy python submission (verdict: Runtime Error):
import math
import re
import copy
import sys

a,b,k = map(int,input().split())
l = list(range(a,b+1))
for i in l[:k]:
    print(i)
l = l[k:len(l)]
le = len(l)
k = le-k
if k < 0:
    k = 0
for i in l[k:le]:
    print(i)

Fixed submission:
import math
import re
import copy
import sys

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

for i in range(a,min(a+k,b+1)):
    print(i)

for j in range(max(b-k+1,i+1),b+1,1):
    print(j)

Buggy python submission (verdict: Runtime Error):
import math
import re
import copy
import sys

a,b,k = map(int,input().split())
l = list(range(a,b+1))
for i in l[:k]:
    print(i)
l = l[k:len(l)]
le = len(l)
k = le-k
if k < 0:
    k = 0
for i in l[k:le]:
    print(i)

Fixed submission:
import math
import re
import copy
import sys

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

for i in range(a,min(a+k,b+1)):
    print(i)

for j in range(max(b-k+1,i+1),b+1,1):
    print(j)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import copy
import re
mod = 10**9+7

n = int(input())
neko = 1
for i in range(n):
    neko *= (i+1)
print(neko%mod)

Fixed submission:
import math
import copy
import re
mod = 10**9+7

n = int(input())
neko = math.factorial(n)
print(neko%mod)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    B=A[::-1]
    ans=1
    if A[-1]<=0:
        if k%2==0:
            for a in A[:k]:
                ans*=a
                ans%=mod
        else:
            for a in B[:k]:
                ans*=a
                ans%=mod
        return ans
    if n==k:
        for a in A:
            ans*=a
            ans%=mod
        return ans
    Neg=[]; Pos=[]
    zero=0
    for a in A:
        if a>0:
            Pos.append(a)
        elif a<0:
            Neg.append(a)
        else:
            zero+=1
    if zero>n-k:
        return 0
    pos=len(Pos); neg=len(Neg)
    if neg==0:
        for a in B[:k]:
            ans*=a
            ans%=mod
        return ans
    for _ in range(zero):
        Neg.append(0)
    Neg.reverse()
    Pos.reverse()
    cnt=k
    while cnt>pos:
        cnt-=2
    Pos=Pos[:cnt]
    for p in Pos:
        ans*=p
        ans%=mod
    for _ in range(k-cnt):
        ans*=Neg.pop()
    while len(Pos)>=2 and len(Neg)>=2:
        p1=Pos.pop()
        p2=Pos.pop()
        n1=Neg.pop()
        n2=Neg.pop()
        if p1*p2<=n1*n2:
            ans*=inv(p1)*inv(p2)
            ans*=n1
            ans%=mod
            ans*=n2
            ans%=mod
        else:
            break
    return ans
    
if __name__=='__main__':
    print(main())

Fixed submission:
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    B=A[::-1]
    ans=1
    if A[-1]<=0:
        if k%2==0:
            for a in A[:k]:
                ans*=a
                ans%=mod
        else:
            for a in B[:k]:
                ans*=a
                ans%=mod
        return ans
    if n==k:
        for a in A:
            ans*=a
            ans%=mod
        return ans
    Neg=[]; Pos=[]
    zero=0
    for a in A:
        if a>0:
            Pos.append(a)
        elif a<0:
            Neg.append(a)
        else:
            zero+=1
    if zero>n-k:
        return 0
    pos=len(Pos); neg=len(Neg)
    if neg==0:
        for a in B[:k]:
            ans*=a
            ans%=mod
        return ans
    for _ in range(zero):
        Neg.append(0)
    Neg.reverse()
    Pos.reverse()
    cnt=k
    while cnt>pos:
        cnt-=2
    Pos=Pos[:cnt]
    for p in Pos:
        ans*=p
        ans%=mod
    for _ in range(k-cnt):
        ans*=Neg.pop()
        ans%=mod
    while len(Pos)>=2 and len(Neg)>=2:
        p1=Pos.pop()
        p2=Pos.pop()
        n1=Neg.pop()
        n2=Neg.pop()
        if p1*p2<=n1*n2:
            ans*=inv(p1)*inv(p2)
            ans*=n1
            ans%=mod
            ans*=n2
            ans%=mod
        else:
            break
    return ans
    
if __name__=='__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
from random import seed, randint

def calc(d,C,S,T):
    Last=[0]*26
    score=0
    for day,t in enumerate(T):
        t-=1
        Last[t]=day+1
        score+=S[day][t]
        for i,c in enumerate(C):
            score-=c*(day+1-Last[i])
    return score

def main():
    d=int(input())
    C=tuple(map(int,input().split()))
    S=[tuple(map(int,input().split())) for _ in range(d)]
    Ans=[0]*d
    Last=[0]*26
    
    #貪欲法
    for day in range(d):
        ans=0
        score=-float('inf')
        for t in range(26):
            TmpList=Last[:]
            tmp_score=S[day][t]
            TmpList[t]=day+1
            for i,c in enumerate(C):
                tmp_score-=c*(day+1-TmpList[i])
            if tmp_score>score:
                score=tmp_score
                ans=t+1
        Ans[day]=ans
        Last[ans-1]=day
    
    score=calc(d,C,S,Ans)
    #print(Ans)
    #print(score)
    
    #局所探索法
    m=15000
    for i in range(m):
        T=Ans[:]
        seed(i)
        d_idx=randint(0,d-1)
        q=randint(1,26)
        #print(d_idx,q)
        T[d_idx]=q
        tmp=calc(d,C,S,T)
        if tmp>score:
            score=tmp
            Ans=T[:]
    #print(Ans)
    #print(score)
    
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()

Fixed submission:
import sys
input=sys.stdin.readline
from random import seed, randint

def calc(d,C,S,T):
    Last=[0]*26
    score=0
    for day,t in enumerate(T):
        t-=1
        Last[t]=day+1
        score+=S[day][t]
        for i,c in enumerate(C):
            score-=c*(day+1-Last[i])
    return score

def main():
    d=int(input())
    C=tuple(map(int,input().split()))
    S=[tuple(map(int,input().split())) for _ in range(d)]
    T=[(i%26)+1 for i in range(d)]
    score=calc(d,C,S,T)
    Ans=T[:]
    #print(score)
    m=10000
    for i in range(m):
        seed(i)
        d_idx=randint(0,d-1)
        q=randint(1,26)
        #print(d_idx,q)
        T[d_idx]=q
        tmp=calc(d,C,S,T)
        if tmp>score:
            score=tmp
            Ans=T[:]
    #print(score)
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    DP=[[0]*(s+1) for _ in range(n+1)]
    p=1
    for i in range(n+1):
        DP[i][0]=p
        p*=2
    for i,a in enumerate(A):
        for j in range(1,s+1):
            DP[i+1][j]=DP[i][j]*2
            if j>=a:
                DP[i+1][j]+=DP[i][j-a]
            DP[i+1][j]%=mod
    print(DP[-1][-1])
    #print(DP)
    
if __name__=='__main__':
    main()

Fixed submission:
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    DP=[[0]*(s+1) for _ in range(n+1)]
    p=1
    for i in range(n+1):
        DP[i][0]=p
        p*=2
        p%=mod
    for i,a in enumerate(A):
        for j in range(1,s+1):
            DP[i+1][j]=DP[i][j]*2
            if j>=a:
                DP[i+1][j]+=DP[i][j-a]
            DP[i+1][j]%=mod
    print(DP[-1][-1])
    #print(DP)
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n,m,q=map(int,input().split())
    ABCD=[list(map(int,input().split())) for _ in range(q)]
    ans=0
    L=list(range(1,m+1))
    for Q in combinations_with_replacement(L,n):
        Q=list(sorted(Q))
        tmp=0
        for a,b,c,d in ABCD:
            if Q[b-1]-Q[a-1]==c:
                tmp+=d
        ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
from itertools import combinations_with_replacement
def main():
    n,m,q=map(int,input().split())
    ABCD=[list(map(int,input().split())) for _ in range(q)]
    ans=0
    L=list(range(1,m+1))
    for Q in combinations_with_replacement(L,n):
        Q=list(sorted(Q))
        tmp=0
        for a,b,c,d in ABCD:
            if Q[b-1]-Q[a-1]==c:
                tmp+=d
        ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
    C=Counter(M)
    ans=0
    for _,m in C.items():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    M=[0]
    p=1
    for s in S[::-1]:
        x=int(s)
        M.append((M[-1]+x*p)%mod)
        p*=10
    C=Counter(M)
    ans=0
    for _,m in C.items():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
print('Yes' if c−a−b>0 and 4*a*b<(c−a−b)**2 else 'No')

Fixed submission:
a,b,c=map(int,input().split())
print('Yes' if (c>a+b and (c-a-b)**2>4*a*b) else 'No')
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline

def dist(a,b,c,d,P3):
    for p in P3:
        da,ma=divmod(a,p)
        dc,mc=divmod(c,p)
        if da!=dc:
            return abs(a-c)+abs(b-d)
        if da!=1:
            a,c=ma,mc
            continue
        db,mb=divmod(b,p)
        dd,md=divmod(d,p)
        if db==dd:
            a,c=ma,mc
            continue
        return min(ma+mc+2,2*pi-(ma+mc))+abs(b-d)
    return abs(b-d)

def main():
    q=int(input())
    P3=[pow(3,i) for i in reversed(range(30))]
    for _ in range(q):
        a,b,c,d=map(lambda x: int(x)-1,input().split())
        print(max(dist(a,b,c,d,P3),dist(b,a,d,c,P3)))

if __name__=='__main__':
    main()

Fixed submission:
import sys
input=sys.stdin.readline

def dist(a,b,c,d,P3):
    for p in P3:
        da,ma=divmod(a,p)
        dc,mc=divmod(c,p)
        if da!=dc:
            return abs(a-c)+abs(b-d)
        if da!=1:
            a,c=ma,mc
            continue
        db,mb=divmod(b,p)
        dd,md=divmod(d,p)
        if abs(db-dd)<2:
            a,c=ma,mc
            continue
        return min(ma+mc+2,2*p-(ma+mc))+abs(b-d)
    return abs(a-c)+abs(b-d)

def main():
    q=int(input())
    P3=[pow(3,i) for i in reversed(range(30))]
    for _ in range(q):
        a,b,c,d=map(lambda x: int(x)-1,input().split())
        print(max(dist(a,b,c,d,P3),dist(b,a,d,c,P3)))

if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

def main():
    s=input().strip()
    q=int(input())
    cnt=0
    Q=[]
    for _ in range(q):
        query=input().strip()
        if query=='1':
            cnt+=1
        else:
            _,f,c=query.split()
            Q.append((cnt,int(f),c))
    if cnt%2==0:
        ans=s
    else:
        ans=s[::-1]
    for a,f,c in Q:
        if (cnt-a+f)%2==0:
            ans+=c
        else:
            ans=c+ans
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
import sys
input=sys.stdin.readline
from collections import deque

def main():
    S=deque(input().strip())
    q=int(input())
    rev=0
    for _ in range(q):
        query=input().strip()
        if query=='1':
            rev^=1
        else:
            _,f,c=query.split()
            if (int(f)+rev)%2:
                S.appendleft(c)
            else:
                S.append(c)
    if rev:
        S.reverse()
    print(''.join(S))
    
if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

def main():
    s=input().strip()
    q=int(input())
    cnt=0
    Q=[]
    for _ in range(q):
        query=input().strip()
        if query=='1':
            cnt+=1
        else:
            _,f,c=query.split()
            Q.append((cnt,int(f),c))
    if cnt%2==0:
        ans=s
    else:
        ans=s[::-1]
    for a,f,c in Q:
        if (cnt-a+f)%2==0:
            ans+=c
        else:
            ans=c+ans
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
import sys
input=sys.stdin.readline
from collections import deque

def main():
    S=deque(input().strip())
    q=int(input())
    rev=0
    for _ in range(q):
        query=input().strip()
        if query=='1':
            rev^=1
        else:
            _,f,c=query.split()
            if (int(f)+rev)%2:
                S.appendleft(c)
            else:
                S.append(c)
    if rev:
        S.reverse()
    print(''.join(S))
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in tuple(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    d=defaultdict(int)
    tmp=0
    ans=0
    for i,s in enumerate(reversed(S)):
        tmp+=s*pow(10,i)
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

Fixed submission:
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in tuple(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    d=defaultdict(int)
    tmp=0
    digit=1
    ans=0
    for i,s in enumerate(reversed(S)):
        tmp+=s*digit
        digit*=10
        digit%=p
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in list(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    S.reverse()
    d=defaultdict(int)
    tmp=0
    ans=0
    for i,s in enumerate(S):
        tmp+=s*pow(10,i)
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

Fixed submission:
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in tuple(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    d=defaultdict(int)
    tmp=0
    digit=1
    ans=0
    for i,s in enumerate(reversed(S)):
        tmp+=s*digit
        digit*=10
        digit%=p
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
from string import ascii_lowercase

class BIT(): #1-indexed
    def __init__(self,n): #n: 要素数
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x): #i番目(1-indexed)にxを加算
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_1_to_i(self,i): #1番目からi番目(含む)までの総和(1-indexed)
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def sum_i_to_j(self,i,j): #i番目からj番目(含む)までの総和(1-indexed)
        return self.sum_1_to_i(j)-self.sum_1_to_i(i-1)
    def reset(self): #初期化
        self.bit=[0]*(self.size+1)

def main():
    A=ascii_lowercase
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=list(input())
    L=[BIT(n) for _ in range(26)]
    for i,s in enumerate(S):
        k=D[s]
        L[k].add(i+1,1)
    q=int(input())
    for _ in range(q):
        k,a,b=input().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            l1=D[s]
            l2=D[b]
            L[l2].add(i+1,1)
            L[l1].add(i+1,-1)
        else:
            l=int(a); r=int(b)
            ans=0
            for i in range(26):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
import sys
input=sys.stdin.readline
from string import ascii_lowercase

class BIT(): #1-indexed
    def __init__(self,n): #n: 要素数
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x): #i番目(1-indexed)にxを加算
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_1_to_i(self,i): #1番目からi番目(含む)までの総和(1-indexed)
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def sum_i_to_j(self,i,j): #i番目からj番目(含む)までの総和(1-indexed)
        return self.sum_1_to_i(j)-self.sum_1_to_i(i-1)
    def reset(self): #初期化
        self.bit=[0]*(self.size+1)

def main():
    A=ascii_lowercase
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=list(input().strip())
    L=[BIT(n) for _ in range(26)]
    for i,s in enumerate(S):
        L[D[s]].add(i+1,1)
    q=int(input())
    for _ in range(q):
        k,a,b=input().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            L[D[b]].add(i+1,1)
            L[D[s]].add(i+1,-1)
            S[i]=b
        else:
            l=int(a); r=int(b)
            ans=0
            for i in range(26):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    l=1
    for a in A:
        l=lcm(l,a)
    ans=0
    for a in A:
        ans+=l//a
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Fixed submission:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
def modinv(k,mod):
    return pow(k,mod-2,mod)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    l=1
    for a in A:
        l=lcm(l,a)
    l%=mod
    ans=0
    for a in A:
        ans+=l*modinv(a,mod)
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()