Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
s=str(input())
s=list(s)
if s[0]!="A":
  s.insert(0,"A")
if len(s)>=4:
  if s[4]!="A":
    s.insert(4,"A")
if len(s)>=6:
  if s[6]!="A":
    s.insert(6,"A")
if s[len(s)-1]!="A":
  s.append("A")
if "".join(s)=="AKIHABARA":
  print("YES")
else:
  print("NO")

Fixed submission:
s=str(input())
s=list(s)
if s[0]!="A":
  s.insert(0,"A")
if len(s)>=5:
  if s[4]!="A":
    s.insert(4,"A")
if len(s)>=7:
  if s[6]!="A":
    s.insert(6,"A")
if s[len(s)-1]!="A":
  s.append("A")
if "".join(s)=="AKIHABARA":
  print("YES")
else:
  print("NO")

Buggy python submission (verdict: Runtime Error):
s=str(input())
s=list(s)
if s[0]!="A":
  s.insert(0,"A")
if s[4]!="A":
  s.insert(4,"A")
if s[6]!="A":
  s.insert(6,"A")
if s[8]!="A":
  s.insert(8,"A")
if "".join(s)=="AKIHABARA":
  print("YES")
else:
  print("NO")

Fixed submission:
s=str(input())
s=list(s)
if s[0]!="A":
  s.insert(0,"A")
if len(s)>=5:
  if s[4]!="A":
    s.insert(4,"A")
if len(s)>=7:
  if s[6]!="A":
    s.insert(6,"A")
if s[len(s)-1]!="A":
  s.append("A")
if "".join(s)=="AKIHABARA":
  print("YES")
else:
  print("NO")
Buggy python submission (verdict: Runtime Error):
x,y=map(int,input().split())
if x<y:
  print("<")
elif x>y:
  print(">")
else:
  print("=")

Fixed submission:
x,y=map(str,input().split())
if x<y:
  print("<")
elif x>y:
  print(">")
else:
  print("=")
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
count=0
import bisect
for i in range(0,n):
  tempb=bisect.bisect_right(b,a[i])
  if tempb!=len(b):
    for j in range(tempb,n):
      tempc=bisect.bisect_right(c,b[j])
      tempcl=n-tempc
      count=count+tempcl
print(count)

Fixed submission:
import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
  temp1=bisect.bisect_left(a,b[i])
  temp2=bisect.bisect(c,b[i])
  ans=ans+temp1*(n-temp2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
import collections
#d=collections.Counter(d)
t=collections.Counter(t)
for i in t.items():
  if i[0] not in d:
    print("NO")
    break
  if i[0] in d and i[1]>d.count(i[0]):
    print("NO")
    break
else:
  print("YES")


Fixed submission:
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
import collections
d=collections.Counter(d)
t=collections.Counter(t)
for i in t.items():
  if i[0] not in d:
    print("NO")
    break
  elif i[0] in d and i[1]>d[i[0]]:
    print("NO")
    break
else:
  print("YES")

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
for i in range(m):
  if t.count(t[i])>d.count(t[i]):
    print("NO")
    break
else:
  print("YES")


Fixed submission:
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
import collections
d=collections.Counter(d)
t=collections.Counter(t)
for i in t.items():
  if i[0] not in d:
    print("NO")
    break
  elif i[0] in d and i[1]>d[i[0]]:
    print("NO")
    break
else:
  print("YES")
Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f=map(int,input().split())
i=0
answ=0
anss=0
cnt=0
while 100*a*i<=f:
  j=0
  while 100*a*i+100*b*j<=f:
    k=0
    while c*k<=(a*i+b*j)*e:
      l=((a*i+b*j)*e-c*k)//d
      if (a*i+b*j+c*k+d*l)!=0:
        if cnt<100*(c*k+d*l)/(a*i+b*j+c*k+d*l):
          if (a*i+b*j)*100+c*k+d*l<=f:
            cnt=100*(c*k+d*l)/(a*i+b*j+c*k+d*l)
            answ=(a*i+b*j)*100
            anss=c*k+d*l
      l=(f-(a*i+b*j)*100-c*k)//d
      if (a*i+b*j+c*k+d*l)!=0:
        if cnt<100*(c*k+d*l)/(a*i+b*j+c*k+d*l):
          if c*k+d*l<=(a*i+b*j)*e
            cnt=100*(c*k+d*l)/(a*i+b*j+c*k+d*l)
            answ=(a*i+b*j)*100
            anss=c*k+d*l      
      k=k+1
    j=j+1
  i=i+1
if 100*a==f:
  print(100*a,0)
else:
  print(answ+anss,anss)

Fixed submission:
a,b,c,d,e,f=map(int,input().split())
i=0
answ=0
anss=0
cnt=0
while 100*a*i<=f:
  j=0
  while 100*a*i+100*b*j<=f:
    k=0
    while c*k<=(a*i+b*j)*e:
      l=0
      if (a*i+b*j+c*k+d*l)!=0:
        if cnt<100*(c*k+d*l)/(a*i+b*j+c*k+d*l):
          if (a*i+b*j)*100+c*k+d*l<=f:
            cnt=100*(c*k+d*l)/(a*i+b*j+c*k+d*l)
            answ=(a*i+b*j)*100
            anss=c*k+d*l
      l=((a*i+b*j)*e-c*k)//d
      if l>0:
        if (a*i+b*j+c*k+d*l)!=0:
          if cnt<100*(c*k+d*l)/(a*i+b*j+c*k+d*l):
            if (a*i+b*j)*100+c*k+d*l<=f:
              cnt=100*(c*k+d*l)/(a*i+b*j+c*k+d*l)
              answ=(a*i+b*j)*100
              anss=c*k+d*l
      l=(f-(a*i+b*j)*100-c*k)//d
      if l>0:
        if (a*i+b*j+c*k+d*l)!=0:
          if cnt<100*(c*k+d*l)/(a*i+b*j+c*k+d*l):
            if c*k+d*l<=(a*i+b*j)*e:
              cnt=100*(c*k+d*l)/(a*i+b*j+c*k+d*l)
              answ=(a*i+b*j)*100
              anss=c*k+d*l
      k=k+1
    j=j+1
  i=i+1
temp=0
i=0
while 100*a*i<=f:
  j=0
  while 100*a*i+100*b*j<=f:
    temp=max(temp,100*a*i+100*b*j)
    j=j+1
  i=i+1
if 100*a+c>f:
  print(100*a,0)
elif temp//100*e<c:
  print(temp,0)
else:
  print(answ+anss,anss)
Buggy python submission (verdict: Runtime Error):
s=str(input())
s=list(s)
ans=[]
for i in range(0,len(s)):
  if s%2==0:
    ans.append(s[i])
print("".join(ans))

Fixed submission:
s=str(input())
s=list(s)
ans=[]
for i in range(0,len(s)):
  if i%2==0:
    ans.append(s[i])
print("".join(ans))
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
temp=[0]*max(a)
for i in range(n):
  temp[a[i]-1]=temp[a[i]-1]+1
ans=0
for i in range(1,max(a)-1):
  ans=max(ans,temp[i-1]+temp[i]+temp[i+1])
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
temp=[0]*(max(a)+1)
for i in range(n):
  temp[a[i]]=temp[a[i]]+1
ans=0
if max(a)==0 or max(a)==1:
  print(n)
else:
  for i in range(1,max(a)):
    ans=max(ans,temp[i-1]+temp[i]+temp[i+1])
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
at=list(set(a))
ans=0
for i in range(len(at)):
  cnt=0
  for j in range(n):
    if a[j]==at[i] or a[j]==at[i]+1 or a[j]==at[i]-1:
      cnt=cnt+1
  ans=max(ans,cnt)
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
temp=[0]*(max(a)+1)
for i in range(n):
  temp[a[i]]=temp[a[i]]+1
ans=0
if max(a)==0 or max(a)==1:
  print(n)
else:
  for i in range(1,max(a)):
    ans=max(ans,temp[i-1]+temp[i]+temp[i+1])
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=0
x=1
while x<=max(a)+1:
  ans=max(ans,a.count(x-1)+a.count(x)+a.count(x+1))
  x=x+1
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
temp=[0]*(max(a)+1)
for i in range(n):
  temp[a[i]]=temp[a[i]]+1
ans=0
if max(a)==0 or max(a)==1:
  print(n)
else:
  for i in range(1,max(a)):
    ans=max(ans,temp[i-1]+temp[i]+temp[i+1])
  print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
  if p[i]==i+1:
    ans=ans+1
    if p!=n-1:
      if p[i+1]==i+2:
        ans=ans-1
print(ans)

Fixed submission:
n=int(input())
p=list(map(int,input().split()))
ans=0
i=0
while i<n:
  if p[i]==i+1:
    ans=ans+1
    i=i+1
  i=i+1
print(ans)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
n=int(input())
ans=int(input())
for i in range(1,n):
  t=int(input())
  ans=int(ans*t/gcd(ans,t))
print(ans)

Fixed submission:
from fractions import gcd
n=int(input())
ans=int(input())
for i in range(1,n):
  t=int(input())
  ans=ans*t//gcd(ans,t)
print(int(ans))

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
n=int(input())
t=[0]*n
ans=int(input())
for i in range(1,n):
  t=int(input())
  ans=int(ans*t/gcd(ans,t))
print(ans)

Fixed submission:
from fractions import gcd
n=int(input())
ans=int(input())
for i in range(1,n):
  t=int(input())
  ans=ans*t//gcd(ans,t)
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
temp=sum(a)
ans=99999999999999999
for i in range(1,n):
  temp1=sum(a[0:i])
  ans=min(ans,abs(temp-temp1*2))
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
temp=sum(a)
temp1=a[0]
ans=abs(temp-temp1*2)
for i in range(1,n-1):
  temp1=temp1+a[i]
  ans=min(ans,abs(temp-temp1*2))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=99999999999999999
for i in range(1,n):
  temp1=sum(a[0:i])
  temp2=sum(a[i:n])
  ans=min(ans,abs(temp1-temp2))
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
temp=sum(a)
temp1=a[0]
ans=abs(temp-temp1*2)
for i in range(1,n-1):
  temp1=temp1+a[i]
  ans=min(ans,abs(temp-temp1*2))
print(ans)
Buggy python submission (verdict: Runtime Error):
s=str(input())
s=list(s)
while True:
  del s[len(s)-1]
  if len(s)%2==0:
    count=0
    for i in range(0,int(len(s)/2)):
      if s[i]==s[i+int(len(s)/2)]:
        count=count+1
    if count==int(len(s)/2):
      print(len(s))

Fixed submission:
s=str(input())
s=list(s)
while True:
  del s[len(s)-1]
  if len(s)%2==0:
    count=0
    for i in range(0,int(len(s)/2)):
      if s[i]==s[i+int(len(s)/2)]:
        count=count+1
    if count==int(len(s)/2):
      print(len(s))
      break
Buggy python submission (verdict: Time Limit Exceeded):
s=int(input())
a=list(map(int,input().split()))
b=[]*s
if s%2==0:
  for i in range(0,s):
    if i%2==0:
      b.append(a[i])
    if i%2!=0:
      b.insert(0,a[i])
else:
  for i in range(0,s):
    if i%2!=0:
      b.append(a[i])
    if i%2==0:
      b.insert(0,a[i])  
print(" ".join(map(str,b)))

Fixed submission:
s=int(input())
a=list(map(int,input().split()))
b=[]
if s%2!=0:
  for i in range(s-1,-1,-2):
    b.append(a[i])
  for i in range(1,s,2):
    b.append(a[i])
else:
  for i in range(s-1,0,-2):
    b.append(a[i])
  for i in range(0,s,2):
    b.append(a[i])
print(" ".join(map(str,b)))

Buggy python submission (verdict: Time Limit Exceeded):
#from collections import deque
s=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(0,s):
  b.append(a[i])
  b=b[::-1]
print(" ".join(map(str,b)))

Fixed submission:
s=int(input())
a=list(map(int,input().split()))
b=[]
if s%2!=0:
  for i in range(s-1,-1,-2):
    b.append(a[i])
  for i in range(1,s,2):
    b.append(a[i])
else:
  for i in range(s-1,0,-2):
    b.append(a[i])
  for i in range(0,s,2):
    b.append(a[i])
print(" ".join(map(str,b)))
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
temp=[0,0,0,0,0,0,0,0]
r=0
for i in range(n):
  if a[i]>=3200:
    r=r+1
  elif a[i]>=2800:
    temp[7]=1
  elif a[i]>=2400:
    temp[6]=1
  elif a[i]>=2000:
    temp[5]=1
  elif a[i]>=1600:
    temp[4]=1
  elif a[i]>=1200:
    temp[3]=1
  elif a[i]>=800:
    temp[2]=1
  elif a[i]>=400:
    temp[1]=1
  else:
    temp[0]=1
print(sum(temp),temp(sum)+r)  

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
temp=[0,0,0,0,0,0,0,0]
r=0
for i in range(n):
  if a[i]>=3200:
    r=r+1
  elif a[i]>=2800:
    temp[7]=1
  elif a[i]>=2400:
    temp[6]=1
  elif a[i]>=2000:
    temp[5]=1
  elif a[i]>=1600:
    temp[4]=1
  elif a[i]>=1200:
    temp[3]=1
  elif a[i]>=800:
    temp[2]=1
  elif a[i]>=400:
    temp[1]=1
  else:
    temp[0]=1
if sum(temp)==0:
  print(1,r)
else:
  print(sum(temp),sum(temp)+r)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
temp={}
a=[]
for i in range(n):
  at,bt=map(int,input().split())
  if at in a:
    temp[at]=temp[at]+bt
  else:
    temp[at]=bt
    a.append(at)
a.sort()
cnt=0
for i in range(n):
  cnt=cnt+temp[a[i]]
  if cnt>=k:
    print(a[i])
    break
  

Fixed submission:
n,k=map(int,input().split())
temp={}
a=[0]*n
for i in range(n):
  at,bt=map(int,input().split())
  a[i]=at
  temp[at]=temp.get(at, 0)+bt
a=list(set(a))
a.sort()
cnt=0
for i in range(n):
  cnt=cnt+temp[a[i]]
  if cnt>=k:
    print(a[i])
    break
Buggy python submission (verdict: Runtime Error):
o=str(input())
e=str(input())
s="A"
for i in range(0,len(o)):
  s=s+o[i]+e[i]
s=s.lstrip("A")
print(s)

Fixed submission:
o=str(input())
e=str(input())
s="A"
l=min(len(o),len(e))
for i in range(0,l):
  s=s+o[i]+e[i]
if len(o)<len(e):
  s=s+e[len(e)-1]
elif len(o)>len(e):
  s=s+o[len(o)-1]
s=s.lstrip("A")
print(s)
Buggy python submission (verdict: Runtime Error):
w,a,b=map(int,input().split())
print(min(abs(b-a-w),abs(a-b),abs(b+w-a))


Fixed submission:
w,a,b=map(int,input().split())
if (a<=b and a+w>=b) or (b<=a and b+w>=a):
  print(0)
else:
  print(min(abs(b-a-w),abs(b+w-a)))
Buggy python submission (verdict: Runtime Error):
x=int(input())
temp=0
for i in range(1,x):
  temp=temp+i
  if temp>=x:
    break
print(i)

Fixed submission:
x=int(input())
temp=0
for i in range(1,x+1):
  temp=temp+i
  if temp>=x:
    break
print(i)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
import math
power=1
for i in range(0,N):
  power=power*(i+1)
print(power%(10**9+7))

Fixed submission:
N=int(input())
import math
power=math.factorial(N)
print(power%(10**9+7))

Buggy python submission (verdict: Runtime Error):
N=int(input())
import math
power=1
for i in range(0,n):
  power=power*(i+1)
print(power%(10**9+7))

Fixed submission:
N=int(input())
import math
power=math.factorial(N)
print(power%(10**9+7))
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
print(max(a*b),(c*d))

Fixed submission:
a,b,c,d=map(int,input().split())
print(max((a*b),(c*d)))
Buggy python submission (verdict: Time Limit Exceeded):
k,s=map(int,input().split())
temp=[x+y+z for z in range(k+1) for y in range(k+1) for x in range(k+1)].count(s)
print(temp)


Fixed submission:
k,s=map(int,input().split())
temp=[1 for y in range(k+1) for x in range(k+1) if 0<=s-x-y<=k]
print(len(temp))

Buggy python submission (verdict: Runtime Error):
k,s=map(int,input().split())
x=[0]*k
for i in range(0,k):
  x[i]=i
x.append(k)
a=int(s/3)-1
count=0
for i in range(0,len(x)):
  stemp=s-x[i]
  for j in range(0,stemp+1):
    if s-x[i]-x[j] in x:
      count=count+1
print(count)


Fixed submission:
k,s=map(int,input().split())
temp=[1 for y in range(k+1) for x in range(k+1) if 0<=s-x-y<=k]
print(len(temp))

Buggy python submission (verdict: Time Limit Exceeded):
k,s=map(int,input().split())
x=[0]*k
for i in range(0,k):
  x[i]=i
x.append(k)
a=int(s/3)-1
#y=x[-a:]
count=0
for i in range(0,len(x)):
  for j in range(0,len(x)):
    if s-x[i]-x[j] in x:
      count=count+1
print(count)


Fixed submission:
k,s=map(int,input().split())
temp=[1 for y in range(k+1) for x in range(k+1) if 0<=s-x-y<=k]
print(len(temp))
Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(1,n):
  temp=max(0,a[i]+a[i-1]-x):
  ans=ans+temp
  a[i]=a[i]-temp
print(ans)

Fixed submission:
N,x=map(int,input().split())
A=list(map(int,input().split()))+[0]
ans=0
for i in range(N):
  eated=max(0,A[i]+A[i-1]-x)
  ans+=eated
  A[i]-=eated
print(ans)

Buggy python submission (verdict: Runtime Error):
A=list(map(int,input().split()))+[0]
ans=0
for i in range(N):
    eated=max(0,A[i]+A[i-1]-x)
    ans+=eated
    A[i]-=eated
print(ans)

Fixed submission:
N,x=map(int,input().split())
A=list(map(int,input().split()))+[0]
ans=0
for i in range(N):
  eated=max(0,A[i]+A[i-1]-x)
  ans+=eated
  A[i]-=eated
print(ans)

Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
count=0
for i in range(0,n-1):
  if a[i]+a[i+1]>x:
    ans=ans+a[i]+a[i+1]-x
    a[i+1]=a[i+1]-(a[i]+a[i+1]-x)
for i in range(n-1,0,-1):
  if a[i]+a[i+1]>x:
    count=count+a[i]+a[i+1]-x
    a[i]=a[i]-(a[i]+a[i+1]-x)
print(min(ans,count))

Fixed submission:
N,x=map(int,input().split())
A=list(map(int,input().split()))+[0]
ans=0
for i in range(N):
  eated=max(0,A[i]+A[i-1]-x)
  ans+=eated
  A[i]-=eated
print(ans)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
a=[]
for i in range(h):
  at=list(str(input()))
  a.append(at)
i=0
j=0
t=0
while True:
  if a[i][j+1]=="#":
    for k in range(i+1,h):
      if a[k][j]=="#":
        t=1
        break
    else:
      j=j+1
  elif a[i+1][j]=="#":
    for k in range(j+1,w):
      if a[i][k]=="#":
        t=1
        break
    else:
      i=i+1
  if t==1:
    print("Impossible")
    break
  elif i==h-1 and j==w-1:
    print("Possible")
    break

Fixed submission:
h,w=map(int,input().split())
a=[]
for i in range(h):
  at=list(str(input()))
  a.append(at)
i=0
j=0
t=0
while True:
  if j!=w-1:
    if a[i][j+1]=="#":
      for k in range(i+1,h):
        if a[k][j]=="#":
          t=1
          break
      else:
        j=j+1
  if i!=h-1:
    if a[i+1][j]=="#":
      for k in range(j+1,w):
        if a[i][k]=="#":
          t=1
          break
      else:
        i=i+1
  if t==1:
    print("Impossible")
    break
  elif i==h-1 and j==w-1:
    print("Possible")
    break
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = np.zeros(n+1, dtype=np.int)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)

Fixed submission:
mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = np.zeros(n, dtype=np.int)
dp[0] = 1
for i in range(n-1):
  for j in range(k):
    dp[i + left[j] : i + right[j] + 1] += dp[i]
    dp[i + left[j] : i + right[j] + 1] %= mod
print(dp[-1])

Fixed submission:
mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)
Buggy python submission (verdict: Runtime Error):
s = int(input())

fact = [1] * s
inv = [1] * s
invf = [1] * s
for i in range(2, s):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(p // i) * inv[p % i] % mod
  invf[i] = invf[i-1] * inv[i] % mod

count = 0
rest = s
for n in range(1, (s + 2) // 3):
  rest -= 3
  count = (count + inv[rest + n - 1] * invf[rest] * invf[n - 1]) % mod
print(count)

Fixed submission:
s = int(input())
mod = 10 ** 9 + 7

fact = [1] * s
inv = [1] * s
invf = [1] * s
for i in range(2, s):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(mod // i) * inv[mod % i] % mod
  invf[i] = invf[i-1] * inv[i] % mod

count = 0
rest = s
for n in range(1, s // 3 + 1):
  rest -= 3
  count = (count + fact[rest + n - 1] * invf[rest] * invf[n - 1]) % mod
print(count)
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7
n = int(input())

a_sum = 0
sq_sum = 0
for a in map(int, input().split()):
  a_sum = (a_sum + a) % mod
  sq_sum = (sq_sum + a * a) % mod
res = (a_sum * a_sum - sq_sum) % mod
print(-(p // 2) % mod * res % mod)

Fixed submission:
mod = 10 ** 9 + 7
n = int(input())

a_sum = 0
sq_sum = 0
for a in map(int, input().split()):
  a_sum = (a_sum + a) % mod
  sq_sum = (sq_sum + a * a) % mod
res = (a_sum * a_sum - sq_sum) % mod
print(-(mod // 2) % mod * res % mod)
Buggy python submission (verdict: Time Limit Exceeded):
def zero_origin(s: str) -> int:
  return int(s) - 1

h, w = map(int, input().split())
ch, cw = map(zero_origin, input().split())
dh, dw = map(zero_origin, input().split())
s = [input() for _ in range(h)]
active = [
  [True if s[i][j] == '.' else False for j in range(w)]
  for i in range(h)]

magic = 0
stack = [(ch, cw)]
active[ch][cw] = False
visited = []
while stack:
  cur_i, cur_j = stack.pop()
  visited.append((cur_i, cur_j))
  for di, dj in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
    i = cur_i + di
    j = cur_j + dj
    if 0 <= i < h and 0 <= j < w and active[i][j]:
      stack.append((i, j))
      active[i][j] = False
  if not active[dh][dw]:
    print(magic)
    break
  if not stack:
    magic += 1
    while visited:
      cur_i, cur_j = visited.pop()
      for i in range(cur_i - 2, cur_i + 3):
        for j in range(cur_j - 2, cur_j + 3):
          if 0 <= i < h and 0 <= j < w and active[i][j]:
            stack.append((i, j))
            active[i][j] = False
else:
  print(-1)

Fixed submission:
def zero_origin(s: str) -> int:
  return int(s) - 1

h, w = map(int, input().split())
ch, cw = map(zero_origin, input().split())
dh, dw = map(zero_origin, input().split())
s = [input() for _ in range(h)]
active = [
  [True if s[i][j] == '.' else False for j in range(w)]
  for i in range(h)]

magic = 0
stack = [(ch, cw)]
active[ch][cw] = False
visited = []
while stack:
  cur_i, cur_j = stack.pop()
  visited.append((cur_i, cur_j))
  for di, dj in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
    i = cur_i + di
    j = cur_j + dj
    if 0 <= i < h and 0 <= j < w and active[i][j]:
      stack.append((i, j))
      active[i][j] = False
  if not active[dh][dw]:
    print(magic)
    break
  if not stack:
    magic += 1
    while visited:
      cur_i, cur_j = visited.pop()
      for i in range(cur_i - 2, cur_i + 3):
        for j in range(cur_j - 2, cur_j + 3):
          if 0 <= i < h and 0 <= j < w and active[i][j]:
            stack.append((i, j))
            active[i][j] = False
else:
  print(-1)
Buggy python submission (verdict: Runtime Error):
h, w, k = map(int, input().split())
mark = [input() for _ in range(h)]
ans = 0

for bit_h in range(1 << h):
  i_list = []
  for i in range(h):
    if bit_h & 1:
      i_list.append(i)
    bit_h >>= 1
  for bit_w in range(1 << w):
    count = 0
    j_list = []
    for j in range(w):
      if bit_w & 1:
        j_list.append(bit_w & 1)
      bit_w >>= 1
    for i in i_list:
      for j in j_list:
        if mark[i][j] = '#':
          count += 1
    if count == k:
      ans += 1
print(ans)

Fixed submission:
h, w, k = map(int, input().split())
mark = [input() for _ in range(h)]
ans = 0

for bit_h in range(1 << h):
  i_list = []
  for i in range(h):
    if bit_h & 1:
      i_list.append(i)
    bit_h >>= 1
  for bit_w in range(1 << w):
    count = 0
    j_list = []
    for j in range(w):
      if bit_w & 1:
        j_list.append(j)
      bit_w >>= 1
    for i in i_list:
      for j in j_list:
        if mark[i][j] == '#':
          count += 1
    if count == k:
      ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n = int(input())
table = np.ones(n + 1, dtype=int)
multiple = np.arange(n + 1)

for i in range(2, n + 1):
  for j in range(i, n + 1, i):
    table[j] += 1
    
print(table @ multiple)

Fixed submission:
n = int(input())

ans = 0
for i in range(1, n + 1):
  k = n // i
  ans += i * k * (k + 1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

x = np.zeros(100_001, dtype=int)
v = np.arange(100_001)

n = int(input())
for a in map(int, input().split()):
  x[a] += 1
q = int(input())
for _ in range(q):
  b, c = map(int, input().split())
  x[c] += x[b]
  x[b] = 0
  print(x @ v)

Fixed submission:
x = [0] * 100_001
value = 0

n = int(input())
for a in map(int, input().split()):
  x[a] += 1
  value += a
q = int(input())
for _ in range(q):
  b, c = map(int, input().split())
  value += (c - b) * x[b]
  x[c] += x[b]
  x[b] = 0
  print(value)