Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
N=int(input())

#約数出す
def divisor(x):
    div=[]
    for i in range(1,int(x**(1/2))+1):
        if x%i==0:
            div.append(i)
            if i!=x//i:
                div.append(x//i)
    return sorted(div)

#累乗数判定
def is_perfect_power(x):
    size=int(math.log2(x)+1)
    for b in range(2,size):
        a=int(math.pow(x,1/b))
        if a**b==x or (a+1**b==x): return a
    return 0
    

A=divisor(N)
z=[]
for i in range(len(A)):
    if len(divisor(A[i]))==2:
        z.append(A[i])
    else:
        x=is_perfect_power(A[i])
        if x!=0:
            if len(divisor(x))==2:
                z.append(A[i])
z=sorted(z)
cnt=0
for i in range(N):
    if N>=z[i]:
        if N%z[i]==0:
            N=N//z[i]
            cnt+=1
    else:
        break
print(cnt)

Fixed submission:
N=int(input())

def divisor(x):
    div=[]
    for i in range(1,int(x**(1/2))+1):
        if x%i==0:
            div.append(i)
            if i!=x//i:
                div.append(x//i)
    return sorted(div)

def factorization(n):
    arr=[]
    temp=n
    for i in range(2,int(n**(1/2))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp//=i
            arr.append([i,cnt])
        
    if temp!=1:
        arr.append([temp,1])

    if arr==[]:
        arr.append([n,1])
    
    return arr

zt=[1]
ans=0
while N>1:
    for i in divisor(N):
        if i not in zt:  
            if len(factorization(i))==1:
                z=i
                zt.append(z)
                break
    if z==0:
        break
    N=N//z
    ans+=1
    z=0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(ans)

Fixed submission:
from math import gcd
K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans+=gcd(gcd(a,b),c)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans+=gcd(gcd(a,b),c)
print(ans)

Fixed submission:
from math import gcd
K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans+=gcd(gcd(a,b),c)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
cntR,cntG,cntB=S.count('R'),S.count('G'),S.count('B')

a=[cntR]*N
b=[cntG]*N
c=[cntB]*N
for i in range(N):
    if i==0:
        if S[i]=='R':
            a[i]-=1
        elif S[i]=='G':
            b[i]-=1
        else:
            c[i]-=1
    else:
        a[i],b[i],c[i]=a[i-1],b[i-1],c[i-1]
        if S[i]=='R':
            a[i]-=1
        elif S[i]=='G':
            b[i]-=1
        else:
            c[i]-=1
ans=0
for i in range(N-2):
    p=0
    t=S[i]
    r=0
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            t+=S[j]
            k=2*j-i
            if t=='RG' or t=='GR':
                ans+=c[j]
            elif t=='GB' or t=='BG':
                ans+=a[j]
            else:
                ans+=b[j]
            if k<N and S[k] not in t:
                ans-=1
            t=S[i]

print(ans)

Fixed submission:
N=int(input())
S=input()
cntR,cntG,cntB=S.count('R'),S.count('G'),S.count('B')

ans=cntR*cntG*cntB

for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if k<N and S[k]!=S[i] and S[k]!=S[j]:
                ans-=1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

poe=deque([])
S=input()
for i in range(len(S)):
    poe.append(S[i])
Q=int(input())
P=[]
for i in range(Q):
    a=list(input().split())
    P.append(a)

for i in range(Q):
    if len(P[i])==1:
        poe=list(poe)
        poe=poe[::-1]
        poe=deque(poe)
    else:
        if P[i][1]=='1':
            poe.appendleft(P[i][2])
        else:
            poe.append(P[i][2])

poe=list(poe)
print(''.join(poe))

Fixed submission:
from collections import deque

poe=deque([])
S=input()
for i in range(len(S)):
    poe.append(S[i])
Q=int(input())
P=[]
cnt=0
for i in range(Q):
    a=list(input().split())
    P.append(a)

for i in range(Q):
    if len(P[i])==1:
        cnt+=1
    else:
        P[i][1]=int(P[i][1])+cnt
        if P[i][1]%2==1:
            poe.appendleft(P[i][2])
        else:
            poe.append(P[i][2])

poe=list(poe)
if cnt%2==1:
    poe=poe[::-1]
print(''.join(poe))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=[input() for i in range(N)]
S_set=list(set(S))
poll=[]
for i in range(len(set(S))):
    poll.append((S.count(S_set[i]),S_set[i]))
poll=sorted(poll)[::-1]
x=poll[0][0]
ans=[]
for i in range (len(poll)):
    if x==poll[i][0]:
        ans.append(poll[i][1])
    else:
        break
ans=sorted(ans)
for i in ans:
    print(i)

Fixed submission:
N=int(input())
S=[input() for i in range(N)]
S=sorted(S)
cnt=1
max_cnt=1
ans=[S[0]]
for i in range(N-1):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        cnt=1
    if cnt==max_cnt:
        ans.append(S[i+1])
    if cnt>max_cnt:
        max_cnt=cnt
        ans=[S[i+1]]
ans=sorted(ans)
for i in ans:
    print(i)

Buggy python submission (verdict: Runtime Error):
N=int(input())
S=['x']*N
for i in range(N):
    S[i]=input()
poll=[]
S_set=list(set(S))
for i in range(len(S_set)):
    poll.append((S.count(S_set[i]),S_set[i]))
poll=sorted(poll)[::-1]
x=poll[0][0]
i=0
ans=[]
while True:
    if x==poll[i][0]:
        ans.append(poll[i][1])
        i+=1
    else:
        break
ans=sorted(ans)
for i in range(len(ans)):
    print(ans[i])

Fixed submission:
N=int(input())
S=[input() for i in range(N)]
S=sorted(S)
cnt=1
max_cnt=1
ans=[S[0]]
for i in range(N-1):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        cnt=1
    if cnt==max_cnt:
        ans.append(S[i+1])
    if cnt>max_cnt:
        max_cnt=cnt
        ans=[S[i+1]]
ans=sorted(ans)
for i in ans:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
N,K,S=map(int,input().split())
P=[]
for i in range(N):
    if i<K:
        P.append(S)
    else:
        if S<10**9:
            P.append(S+1)
        else:
            P.append(1)
ans=''
for i in range(N):
    ans=ans+str(P[i])+' '
print(ans)

Fixed submission:
N,K,S=map(int,input().split())
P=[]
for i in range(N):
    if i<K:
        P.append(str(S))
    else:
        if S<10**9:
            P.append(str(S+1))
        else:
            P.append(str(1))

print(" ".join(P))
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())
for i in range(k):
    if a>0:
        a-=1
    else:
        b-=1
    if a==0 and b==0:
        break
print(a,b)

Fixed submission:
a,b,k=map(int,input().split())
if a>k:
    a-=k
elif a+b>k:
    b=b-k+a
    a=0
else:
    a=0
    b=0
print(a,b)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a=list(map(int,input().split()))
cnt=0
k=0
for i in range(N):
    if i+1 in a[k:N]:
        for j in range(k,N):
            if a[j]==i+1:
                cnt+=1
                k=j
                break
    else:
        break
print(N-cnt if cnt>0 else -1)

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
b=[0]*N
cnt=0
for i in range(N):
    if a[i]==cnt+1:
        b[i]=1
        cnt+=1
print(N-sum(b) if sum(b)>0 else -1)
Buggy python submission (verdict: Runtime Error):
import math
a,b,x=map(int,input().split())
y=2*x/(a**2)-b
z=2*x/(a*b)
phai=0
ans=90
if z>a:
    phai=math.atan(a/(b-y))
    phai=math.degrees(phai)
    ans-=phai
else:
    phai=math.atan(z/b)
    phai=math.degrees(phai)
    ans-=phai
print(ans)

Fixed submission:
import math
a,b,x=map(int,input().split())
y=2*x/(a**2)-b
z=2*x/(a*b)
phai=0
ans=90
if x==b*a**2:
   ans=0
else:
    if z>a:
        phai=math.atan(a/(b-y))
        phai=math.degrees(phai)
        ans-=phai
    else:
        phai=math.atan(z/b)
        phai=math.degrees(phai)
        ans-=phai
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=[0]*n
l[:]=map(int,input().split())
ans=0
m=10**3
l=sorted(l)[::-1]
for i in range(n-2):
  m=min(m,l[i])
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if m<l[j]+l[k]:
        ans+=1
      else:
        break
print(ans)

Fixed submission:
import bisect
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N):
    for j in range(i+1,N):
        k=bisect.bisect_left(L,L[i]+L[j])
        ans+=k-j-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=[0]*n
l[:]=map(int,input().split())
ans=0
l=sorted(l)[::-1]
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]<l[j]+l[k]:
        ans+=1
      else:
        break
print(ans)

Fixed submission:
import bisect
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N):
    for j in range(i+1,N):
        k=bisect.bisect_left(L,L[i]+L[j])
        ans+=k-j-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=list(map(int,input().split()))
ans=0
l=sorted(l)[::-1]
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]<l[j]+l[k]:
        ans+=1
print(ans)

Fixed submission:
import bisect
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N):
    for j in range(i+1,N):
        k=bisect.bisect_left(L,L[i]+L[j])
        ans+=k-j-1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))
B=[]
S=''
for i in range(1,n+1):
  B.append(A.index(i)+1)
for i in range(n):
  S+=str(B[i])+' '
print(S)

Fixed submission:
n=int(input())
A=[]*n
A[:]=map(int,input().split())
S=[' ']*n
for i in range(n):
  S[A[i]-1]=str(i+1)
print(' '.join(S))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))
S=''
for i in range(1,n+1):
  S+=str(A.index(i)+1)+' '
print(S)

Fixed submission:
n=int(input())
A=[]*n
A[:]=map(int,input().split())
S=[' ']*n
for i in range(n):
  S[A[i]-1]=str(i+1)
print(' '.join(S))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))
B=[]
S=''
for i in range(1,n+1):
  B.append(i)
for i in range(1,n+1):
  S+=str(B[A.index(i)])+' '
print(S)

Fixed submission:
n=int(input())
A=[]*n
A[:]=map(int,input().split())
S=[' ']*n
for i in range(n):
  S[A[i]-1]=str(i+1)
print(' '.join(S))
Buggy python submission (verdict: Runtime Error):
N=int(input())
A={}
ans=0
for i in range(N):
    s=input()
    s=sorted(s)
    if A.get(s,"Not")=="Not":
        A[s]=1
    else:
        ans+=A[s]
        A[s]+=1
print(ans)

Fixed submission:
N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[]
ans=0
for i in range(N):
    s=input()
    s=sorted(s)
    ans+=A.count(s)
    A.append(s)

print(ans)

Fixed submission:
N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial

def combinations_count(n,r):
    return factorial(n)//(factorial(n-r)*factorial(r))

N=int(input())
A=[]
B=[]
for i in range(N):
    s=input()
    s=sorted(s)
    A.append(s)
    if s not in B:
        B.append(s)

ans=0
for i in range(len(B)):
    if A.count(B[i])>1:
        ans+=combinations_count(A.count(B[i]),2)
print(ans)

Fixed submission:
N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=0
s=[]
for i in range(n):
  a=sorted(input())
  ans+=s.count(a)
  s.append(a)
print(ans)

Fixed submission:
N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def C(n,r):
  a=1
  b=1
  c=1
  for i in range(1,n+1):
    a*=i
  for j in range(1,r+1):
    b*=j
  for k in range(1,n-r+1):
    c*=k
  return a//(b*c)

n,k=map(int,input().split())
for i in range(1,k+1):
  print(C(n-k+1,i)*C(k-1,i-1)%(10**9+7))

Fixed submission:
import math
def C(n,r):
  if n<0 or r<0 or n-r<0:
    return 0
  else:
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))

n,k=map(int,input().split())
for i in range(1,k+1):
  print(C(n-k+1,i)*C(k-1,i-1)%(10**9+7))
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
gcdc=[]
gcdd=[]
for i in range(1,int(c**(1/2))+1):
  if c%i==0:
    gcdc.append(i)
    if i!=c//i:
      gcdc.append(c//i)
for i in range(1,int(d**(1/2))+1):
  if d%i==0:
    gcdd.append(i)
    if i!=d//i:
      gcdd.append(d//i)
E=[]
for i in range(len(gcdc)):
  if gcdc[i] in gcdd:
    E.append(gcdc[i])
e=1
for i in range(len(E)):
  e*=E[i]
f=c*d//e
g=0
h=0
i=0
if a%c==0:
  g=b//c-a//c+1
else:
  g=b//c-a//c
if a%d==0:
  h=b//d-a//d+1
else:
  h=b//d-a//d
if a%f==0:
  i=b//f-a//f+1
else:
  i=b//f-a//f
print(b-a+1-g-h+i)

Fixed submission:
a,b,c,d=map(int,input().split())
gcdc=[]
gcdd=[]
for i in range(1,int(c**(1/2))+1):
  if c%i==0:
    gcdc.append(i)
    if i!=c//i:
      gcdc.append(c//i)
for i in range(1,int(d**(1/2))+1):
  if d%i==0:
    gcdd.append(i)
    if i!=d//i:
      gcdd.append(d//i)
E=[]
for i in range(len(gcdc)):
  if gcdc[i] in gcdd:
    E.append(gcdc[i])
e=max(E)
f=c*d//e
if a%c==0:
  g=b//c-a//c+1
else:
  g=b//c-a//c
if a%d==0:
  h=b//d-a//d+1
else:
  h=b//d-a//d
if a%f==0:
  i=b//f-a//f+1
else:
  i=b//f-a//f
print(b-a+1-g-h+i)
Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
L=list(map(int,input().split()))
count=1
D=0
for i in range(n+1):
  D=D+L[i]
  if D<=x:
    count+=1
  else:
    break
print(count)

Fixed submission:
n,x=map(int,input().split())
L=list(map(int,input().split()))
count=1
D=0
for i in range(n):
  D=D+L[i]
  if D<=x:
    count+=1
  else:
    break
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
A=[0]*(n+1)
A[0]=1
for i in range(1,n+1):
  if i in a:
    A[i]==0
  else:
    A[i]=A[i-1]+A[i-2]
print(A[n]%(10**9+7))

Fixed submission:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a=set(a)
A=[0]*(n+1)
A[0]=1
for i in range(1,n+1):
  if i in a:
    A[i]==0
  else:
    A[i]=A[i-1]+A[i-2]
print(A[n]%(10**9+7))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
A=[]
count=[]
for i in range(m):
  a=int(input())
  if a-1 in A:
    print(0)
    break
  A.append(a)
A=sorted(list(set(A)))
c=1
d=1
for i in range(A[0]-1):
  c=d%(10**9+7)
  d=(c+d)%(10**9+7)
count.append(c)
if m>1:
  for i in range(1,len(A)-1):
    e=1
    f=1
    for j in range(A[i+1]-A[i]-2):
      e=f%(10**9+7)
      f=(e+f)%(10**9+7)
    count.append(e)
a=1
b=1
for i in range(n-A[-1]-1):
  a=b%(10**9+7)
  b=(a+b)%(10**9+7)
count.append(a)
Total=1
for i in range(len(count)):
  Total*=count[i]%(10**9+7)
print(Total%(10**9+7))

Fixed submission:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a=set(a)
A=[0]*(n+1)
A[0]=1
for i in range(1,n+1):
  if i in a:
    A[i]==0
  else:
    A[i]=A[i-1]+A[i-2]
print(A[n]%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))
divsors=[]
for i in range(n):
  for j in range(1,int(A[i]**(1/2)+1)):
    if A[i]%j==0:
      divsors.append(j)
      if j!=A[i]//j:
        divsors.append(A[i]//j)
set_divsors=sorted(list(set(divsors)))[::-1]
for i in range(len(set_divsors)):
  a=divsors.count(set_divsors[i])
  if a==n or a==n-1:
    print(set_divsors[i])
    break

Fixed submission:
n=int(input())
A=[]*n
A[:]=map(int,input().split())

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      
left=[0]*n
right=[0]*n
for i in range(1,n):
  left[i]=gcd(left[i-1],A[i-1])
  right[n-1-i]=gcd(right[n-i],A[n-i])

ans=0
for i,j in zip(left,right):
  ans=max(ans,gcd(i,j))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=list(map(int,input().split()))
divsors=[]
for i in range(n):
  for j in range(1,int(A[i]**(1/2)+1)):
    if A[i]%j==0:
      divsors.append(j)
      if j!=A[i]//j:
        divsors.append(A[i]//j)
set_divsors=sorted(list(set(divsors)))[::-1]
divsors=sorted(divsors)[::-1]
count=[]
for i in range(len(set_divsors)):
  count.append(divsors.count(set_divsors[i]))
for i in range(len(count)):
  if count[i]==n-1 or count[i]==n:
    print(set_divsors[i])
    break

Fixed submission:
n=int(input())
A=[]*n
A[:]=map(int,input().split())

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      
left=[0]*n
right=[0]*n
for i in range(1,n):
  left[i]=gcd(left[i-1],A[i-1])
  right[n-1-i]=gcd(right[n-i],A[n-i])

ans=0
for i,j in zip(left,right):
  ans=max(ans,gcd(i,j))
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
b=[]
count=0
for i in range(len(s)):
  if s[i] in "ATCG":
    count+=1
  else:
    b.append(count)
    count=0
print(max(b))

Fixed submission:
s=input()
b=[]
count=0
for i in range(len(s)):
  if s[i] in "ATCG":
    count+=1
  else:
    b.append(count)
    count=0
b.append(count)
print(max(b))
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
  l,r=map(int,input().split())
  print(s[l-1:r].count('AC'))

Fixed submission:
N,Q=map(int,input().split())
S=input()
B=[0]*N
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        B[i]=B[i-1]+1
    else:
        B[i]=B[i-1]
for i in range(Q):
    l,r=map(int,input().split())
    print(B[r-1]-B[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  for j in range(l-1,r-1):
    if s[j]=='A' and s[j+1]=='C':
      ans+=1
  print(ans)

Fixed submission:
N,Q=map(int,input().split())
S=input()
B=[0]*N
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        B[i]=B[i-1]+1
    else:
        B[i]=B[i-1]
for i in range(Q):
    l,r=map(int,input().split())
    print(B[r-1]-B[l-1])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append([a,b])
AB=sorted(AB)
i=0
amount=0
cost=0
while True:
  if amount+AB[i][1]<=m:
    amount+=AB[i][1]
    cost+=AB[i][0]*AB[i][1]
    i+=1
  else:
    cost+=(m-amount)*AB[i][0]
    print(cost)
    break

Fixed submission:
n,m=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append([a,b])
AB=sorted(AB)
i=0
amount=0
cost=0
while True:
  if amount+AB[i][1]<m:
    amount+=AB[i][1]
    cost+=AB[i][0]*AB[i][1]
    i+=1
  else:
    cost+=(m-amount)*AB[i][0]
    print(cost)
    break
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=[]*n
A[:]=map(int,input().split())

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

ans=10**9
for i in range(n-1):
  for j in range(i+1,n):
    ans=min(ans,gcd(A[i],A[j]))
print(ans)

Fixed submission:
from math import gcd
N=int(input())
A=list(map(int,input().split()))

ans=0
for i in range(N):
    ans=gcd(ans,A[i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
x=list(map(int,input().split()))
x=sorted(x)
l=[0]*(m-1)
for i in range(m-1):
    l[i]=x[i+1]-x[i]
    l=sorted(l)[::-1]
dist=x[m-1]-x[0]-sum(l[:n-1])
print(dist)

Fixed submission:
n,m=map(int,input().split())
x=list(map(int,input().split()))
if n>=m:
    print(0)
    exit()

x=sorted(x)
l=[0]*(m-1)
for i in range(m-1):
    l[i]=x[i+1]-x[i]
    
l=sorted(l)[::-1]
dist=x[m-1]-x[0]-sum(l[:n-1])
print(dist)
Buggy python submission (verdict: Time Limit Exceeded):
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.append(x)
b=[]
m=10**9

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
if n==1:
  print(abs(x-a[0]))
else:
  for i in range(n):
    for j in range(i+1,n+1):
      b.append(abs(a[i]-a[j]))
  for i in range(len(b)-1):
    for j in range(i+1,len(b)):
      m=min(m,gcd(b[i],b[j]))
  print(m)


Fixed submission:
n,x=map(int,input().split())
A=[]*n
A[:]=map(int,input().split())
for i in range(n):
  A[i]=abs(A[i]-x)
if len(A)==1:
  print(A[0])
else:
  def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      
  left=[0]*n
  right=[0]*n
  for i in range(1,n):
    left[i]=gcd(left[i-1],A[i-1])
    right[n-1-i]=gcd(right[n-i],A[n-i])
 
  ans=10**9
  for i,j in zip(left,right):
    ans=min(ans,gcd(i,j))
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
num=[]
for i in range(n):
  num.append(s[:i].count('W')+s[i:].count('E'))
print(min(num))

Fixed submission:
n=int(input())
s=input()
cnt=s.count('E') #西から0番目の人から見たときの向きを変える人数
m=cnt

#西からi番目の人がリーダーの時に向きを変える人の増減について
for i in range(n):
  if s[i]=='E':
    cnt-=1 
  else:
    cnt+=1
  m=min(m,cnt)
print(m)
Buggy python submission (verdict: Runtime Error):
x=int(input())
beki=[]
for b in range(1,x+1):
  for p in range(2,x+1):
    if b**p<=x:
      beki.append(b**p)
    else:
      break
print(max(beki))

Fixed submission:
x=int(input())
if x==1:
  print(1)
else:
  beki=[]
  for b in range(1,x+1):
    for p in range(2,x+1):
      if b**p<=x:
        beki.append(b**p)
      else:
        break
  print(max(beki))
Buggy python submission (verdict: Runtime Error):
a,b,k=map(int,input().split())
l=[int(i) for i in range(a,b+1)]
for i in range(k):
  print(sorted(l)[i])
for i in range(k):
  print(sorted(l)[-k:][i])

Fixed submission:
a,b,k=map(int,input().split())
A=[]
if k>=b-a:
  for i in range(b-a+1):
    print(a+i)
else:
  for i in range(k):
    A.append(a+i)
    if a+i!=b-i:
      A.append(b-i)
  for i in range(len(A)):
    print(sorted(A)[i])
Buggy python submission (verdict: Runtime Error):
S=list(input())
m=list('abcdefghijklmnopqrstuvwxyz')[::-1]

if len(S)<26:
  for i in m[::-1]
        if i not in S:
            S.append(i)
            break
    print(''.join(S))
else:
    x=S[-1]
    for i in range(24,-1,-1):
        if x>S[i]:
            y=m.index(S[i])
            S=S[:i]
            for j in range(y-1,-1,-1):
                if m[j] not in S:
                    S.append(m[j])
                    break
            break
        else:
            x=S[i]
        
        if i==0:
            print(-1)
            exit()
    print(''.join(S))

Fixed submission:
S=list(input())
m=list('abcdefghijklmnopqrstuvwxyz')[::-1]

if len(S)<26:
    for i in m[::-1]:
        if i not in S:
            S.append(i)
            break
    print(''.join(S))
else:
    x=S[-1]
    for i in range(25)[::-1]:
        if x>S[i]:
            y=m.index(S[i])
            S=S[:i]
            for j in range(y)[::-1]:
                if m[j] not in S:
                    S.append(m[j])
                    break
            break
        else:
            x=S[i]
        
        if i==0:
            print(-1)
            exit()
    print(''.join(S))