Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
ans=0
for i in range(K,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))  


Fixed submission:
N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
ans=0
for i in range(K,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))  

Fixed submission:
N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
for i in range(K//2,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
ans=0
for i in range(1,K+1):
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))

Fixed submission:
N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
for i in range(K//2,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
ans=0
for i in range(1,K+1):
  ans+=(i*D[i])%(10**9+7)
print(ans%(10**9+7))

Fixed submission:
N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
for i in range(Q):
  A=list(input().split())
  if len(A)==1:
    S=S[::-1]
  else:
    if int(A[1])==1:
      S=A[-1]+S
    else:
      S=S+A[-1]
print(S)   

Fixed submission:
from collections import deque
S=input()
Q=int(input())
q=deque()
for i in S:
  q.append(i)
cnt=0
for i in range(Q):
  A=list(input().split())
  if int(A[0])==1:
    cnt+=1
  else:
    if int(A[1])==cnt%2+1:
      q.appendleft(A[-1])
    else:
      q.append(A[-1])
if (cnt%2)==0:
  for i in range(len(q)):
    print(q.popleft(),end='')
else:
  for i in range(len(q)):
    print(q.pop(),end='')

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
for i in range(Q):
  A=list(input().split())
  if len(A)==1:
    S=S[::-1]
  else:
    if int(A[1])==1:
      S=A[-1]+S
    else:
      S=S+A[-1]
print(S)   

Fixed submission:
from collections import deque
S=input()
Q=int(input())
q=deque()
for i in S:
  q.append(i)
cnt=0
for i in range(Q):
  A=list(input().split())
  if int(A[0])==1:
    cnt+=1
  else:
    if int(A[1])==cnt%2+1:
      q.appendleft(A[-1])
    else:
      q.append(A[-1])
if (cnt%2)==0:
  for i in range(len(q)):
    print(q.popleft(),end='')
else:
  for i in range(len(q)):
    print(q.pop(),end='')
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
import string 

dic={c:[] for c in string.ascii_lowercase}
N=int(input())
S=list(input())
Q=int(input())
for i in range(len(S)):
  dic[S[i]].append(i+1)
  
for i in range(Q):
  a,b,c=map(str,input().split())
  if a=='1':
    if S[int(b)-1]==c:
      continue
    b=int(b)
    f=S[b-1]
    d=bisect_left(dic[f],b)
    e=bisect_left(dic[c],b)
    dic[f].pop(d)
    dic[c].insert(e,b)
  else:
    ans=0
    b,c=int(b),int(c)
    for j in string.ascii_lowercase:
      d=bisect_left(dic[j],b)
      if d<len(dic[j]):
        if dic[j][d]<=c:
          ans+=1
    print(ans)

Fixed submission:
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
import string 

dic={c:[] for c in string.ascii_lowercase}
N=int(input())
S=list(input())
Q=int(input())
for i in range(len(S)):
  dic[S[i]].append(i+1)
for i in range(Q):
  a,b,c=map(str,input().split())
  if a=='1':
    if S[int(b)-1]==c:
      continue
    d=bisect_left(dic[S[int(b)-1]],int(b))
    e=bisect_left(dic[c],int(b))
    dic[S[int(b)-1]].pop(d)
    dic[c].insert(e,int(b))
  else:
    ans=0
    b,c=int(b),int(c)
    for j in string.ascii_lowercase:
      d=bisect_left(dic[j],b)
      if d<len(dic[j]):
        if dic[j][d]<=c:
          ans+=1
    print(ans)

Fixed submission:
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
  
for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)
Buggy python submission (verdict: Runtime Error):
N,K=map(int, input().split())
AA=list(map(int, input().split()))
A=sorted(AA)
B=sorted(AA)[::-1]
mod=10**9+7

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 = 5*(10**4)+2
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 )

ans=0
for i in range(N-K+1):
  d=(A[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  e=(B[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  ans+=d%mod-e%mod
  ans%=mod
print(ans)


Fixed submission:
N,K=map(int, input().split())
AA=list(map(int, input().split()))
A=sorted(AA)
B=sorted(AA)[::-1]
mod=10**9+7

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**6+1
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 )

ans=0
for i in range(N-K+1):
  d=(A[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  e=(B[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  ans+=d%mod-e%mod
  ans%=mod
print(ans)

Buggy python submission (verdict: Runtime Error):
N,K=map(int, input().split())
AA=list(map(int, input().split()))
A=sorted(AA)
B=sorted(AA)[::-1]
mod=10**9+7

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**4
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 )

ans=0
for i in range(N-K+1):
  d=(A[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  e=(B[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  ans+=d%mod-e%mod
  ans%=mod
print(ans)

Fixed submission:
N,K=map(int, input().split())
AA=list(map(int, input().split()))
A=sorted(AA)
B=sorted(AA)[::-1]
mod=10**9+7

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**6+1
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 )

ans=0
for i in range(N-K+1):
  d=(A[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  e=(B[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  ans+=d%mod-e%mod
  ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
import math
A=[]
for i in range(N):
  x,y=map(int, input().split())
  A.append((x,y))

def c(P1, P2, P3):
    x1, y1 = P1; x2, y2 = P2; x3, y3 = P3
    a = 2*(x1 - x2); b = 2*(y1 - y2); p = x1**2 - x2**2 + y1**2 - y2**2
    c = 2*(x1 - x3); d = 2*(y1 - y3); q = x1**2 - x3**2 + y1**2 - y3**2
    det = a*d - b*c
    x = d*p - b*q; y = a*q - c*p
    if det < 0:
        x = -x; y = -y; det = -det
    x /= det; y /= det
    r = ((x - x1)**2 + (y - y1)**2)
    return x,y,r
  
ans=(200000)**2
for i in range(N-1):
  for j in range(i+1,N):
    f=0
    x1,y1=A[i][0],A[i][1]
    x2,y2=A[j][0],A[j][1]
    x,y=(x1+x2)/2,(y1+y2)/2
    r=(x1-x)**2+(y1-y)**2
    for a,b in A:
      d=(a-x)**2+(b-y)**2
      if d>r:
        f=1
        break
    if f==0:
      ans=min(ans,math.sqrt(r))

if N>2:
  for i in range(N-2):
    for j in range(i,N-1):
      for k in range(j,N):
        f=0
        if c(A[i],A[j],A[k])!=-1:
          x,y,r=c(A[i],A[j],A[k])
          for a,b in A:
            d=(a-x)**2+(b-y)**2
            if d>r:
              f=1
              break
          if f==0:
            ans=min(ans,math.sqrt(r))

print(ans)

Fixed submission:
N=int(input())
A=[]
for i in range(N):
  x,y=map(int, input().split())
  A.append((x,y))

def c(P1, P2, P3):
    x1, y1 = P1; x2, y2 = P2; x3, y3 = P3
    a = 2*(x1 - x2); b = 2*(y1 - y2); p = x1**2 - x2**2 + y1**2 - y2**2
    c = 2*(x1 - x3); d = 2*(y1 - y3); q = x1**2 - x3**2 + y1**2 - y3**2
    det = a*d - b*c
    x = d*p - b*q; y = a*q - c*p
    if det < 0:
        x = -x; y = -y; det = -det
    if det!=0:
      x /= det; y /= det
    r = ((x - x1)**2 + (y - y1)**2)**0.5
    return x,y,r
  
ans=(200000)**2
for i in range(N-1):
  for j in range(i+1,N):
    f=0
    x1,y1=A[i][0],A[i][1]
    x2,y2=A[j][0],A[j][1]
    x,y=(x1+x2)/2,(y1+y2)/2
    r=((x1-x)**2+(y1-y)**2)**0.5
    for a,b in A:
      d=((a-x)**2+(b-y)**2)**0.5
      if d>r:
        f=1
        break
    if f==0:
      ans=min(ans,r)
f=0

if N>2:
  for i in range(N-2):
    for j in range(i+1,N-1):
      for k in range(j+1,N):
        f=0
        x,y,r=c(A[i],A[j],A[k])
        if r>0:
          for a,b in A:
            d=((a-x)**2+(b-y)**2)**0.5
            if d>r:
              f=1
              break
          if f==0:
            ans=min(ans,r)
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
if N%2==1:
  print(0)
else:
  n=N//2
  A=n
  a=0
  b=0
  while A>=5**a:
    a+=1
  while A>=2**b:
    b+=1

cntfive=0  
cnttwo=0
for i in range(1,a):
  cntfive+=n//(5**i)
for j in range(1,b):
  cnttwo+=n//(2**j)

ans=min(cntfive,cnttwo+n)
print(ans)

Fixed submission:
N=int(input())
if N%2==1:
  print(0)
else:
  n=N//2
  A=n
  a=0
  b=0
  while A>=5**a:
    a+=1
  while A>=2**b:
    b+=1

  cntfive=0  
  cnttwo=0
  for i in range(1,a):
    cntfive+=n//(5**i)
  for j in range(1,b):
    cnttwo+=n//(2**j)

  ans=min(cntfive,cnttwo+n)
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
A=[]
for i in range(1,N-1):
  a=list(set(S[0:i]))
  b=len(a)
  c=list(set(S[i+1:N]))
  d=len(c)
  for j in range(b):
    for k in range(d):
      A.append(a[j]+S[i]+c[k])
print(len(set(A)))
  

Fixed submission:
from itertools import product
 
N = int(input())
S = input()
 
cnt = 0
for i, j, k in product("0123456789", repeat=3):
    try:
        x = S.index(i)
        y = S.index(j, x + 1)
        z = S.index(k, y + 1)
    except:
        continue
    cnt += 1
 
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
A=[]
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      A.append(S[i]+S[j]+S[k])
print(len(set(A)))

Fixed submission:
from itertools import product
 
N = int(input())
S = input()
 
cnt = 0
for i, j, k in product("0123456789", repeat=3):
    try:
        x = S.index(i)
        y = S.index(j, x + 1)
        z = S.index(k, y + 1)
    except:
        continue
    cnt += 1
 
print(cnt)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  if c==0:
    print(0)
    exit()
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
D=[-1]*3
ans=1
for i in A:
  c=0
  E=[]
  if i-1==D[0]:
    c+=1
    E.append(0)
  if i-1==D[1]:
    c+=1
    E.append(1)
  if i-1==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  if c==0:
    print(0)
    exit()
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
D=[-1,-1,-1]
ans=1
for i in A:
  c=0
  E=[]
  if i-1==D[0]:
    c+=1
    E.append(0)
  if i-1==D[1]:
    c+=1
    E.append(1)
  if i-1==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  if c==0:
    print(0)
    exit()
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=[[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  A[a].append([b,i])
    
ans = [0]*(n-1)

def col(now,color):
  c=1
  for (b,j) in A[now]:
    if c==color:
      c+=1
    ans[j]=c
    col(b,c)
    c+=1
col(0,0)
print(max(ans))
for a in ans:
  print(a)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

n=int(input())
A=[[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  A[a].append([b,i])
    
ans = [0]*(n-1)

def col(now,color):
  c=1
  for (b,j) in A[now]:
    if c==color:
      c+=1
    ans[j]=c
    col(b,c)
    c+=1
col(0,0)
print(max(ans))
for a in ans:
  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
 
import numpy

ans=3*(10**9)
for i in range(N-1):
  l=(numpy.cumsum(A))[i]
  D=abs(l-(sum(A)-l))
  if ans > D:
    ans=D
  if l >= (sum(A)//2)+1:
    break

print(ans) 

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
 
import numpy as np

def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]

a=(np.cumsum(A))
l=getNearestValue(a, sum(A)/2)

ans=abs(sum(A)-2*l)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
 
import numpy

ans=3*(10**9)
for i in range(N-1):
  l=(numpy.cumsum(A))[i]
  D=abs(l-(sum(A)-l))
  if ans > D:
    ans=D

print(ans) 

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
 
import numpy as np

def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]

a=(np.cumsum(A))
l=getNearestValue(a, sum(A)/2)

ans=abs(sum(A)-2*l)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
 
import itertools
B=list(itertools.accumulate(A))

ans=3*(10**9)
for i in range(N-1):
  l=B[i]
  D=abs(l-(sum(A)-l))
  if ans > D:
    ans=D
 
print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
 
import numpy as np

def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]

a=(np.cumsum(A))
l=getNearestValue(a, sum(A)/2)

ans=abs(sum(A)-2*l)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))

import itertools

ans=3*(10**9)
for i in range(N-1):
  l=list(itertools.accumulate(A))[i]
  D=abs(l-(sum(A)-l))
  if ans > D:
    ans=D

print(ans)

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
 
import numpy as np

def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]

a=(np.cumsum(A))
l=getNearestValue(a, sum(A)/2)

ans=abs(sum(A)-2*l)
print(ans)
Buggy python submission (verdict: Runtime Error):
M=int(input())
ans=0
A=[]
def f(x):
  e=str(x)
  n=len(e)
  l=0
  for i in e:
    l+=int(i)
  if l<10:
    return l
  else:
    f(l)
  
for i in range(M):
  d,c=map(int,input().split())
  ans+=(c-1)+d*c//10
  A.append(f(d*c))
  
ans+=len(A)-1
ans+=(sum(A)-1)//9
print(ans)

Fixed submission:
M=int(input())
k,g=0,0
for i in range(M):
  d,c=map(int,input().split())
  k+=c
  g+=c*d
print((g-1)//9+(k-1))

Buggy python submission (verdict: Runtime Error):
M=int(input())
ans=0
A=[]
def f(x):
  e=str(x)
  n=len(e)
  l=0
  for i in e:
    l+=int(i)
  if l<10:
    return l
  else:
    f(l)
  
for i in range(M):
  d,c=map(int,input().split())
  ans+=(c-1)+d*c//10
  A.append(f(d*c))
if len(A)==1:
  print(ans)
  exit()
cnt=A[0]
for i in A[1:]:
  if cnt+i<10:
    cnt+=i
    ans+=1
  else:
    e=str(cnt+i)
    cnt=int(e[0])+int(e[1])
    ans+=2
print(ans)

Fixed submission:
M=int(input())
k,g=0,0
for i in range(M):
  d,c=map(int,input().split())
  k+=c
  g+=c*d
print((g-1)//9+(k-1))

Buggy python submission (verdict: Runtime Error):
M=int(input())
ans=0
A=[]
def f(x):
  e=str(x)
  n=len(e)
  l=0
  for i in e:
    l+=int(i)
  if l<10:
    return l
  else:
    f(l)
  
for i in range(M):
  d,c=map(int,input().split())
  ans+=(c-1)+d*c//10
  A.append(f(d*c))
  
cnt=A[0]
for i in A[1:]:
  if cnt+i<10:
    cnt+=i
    ans+=1
  else:
    e=str(cnt+i)
    cnt=int(e[0])+int(e[1])
    ans+=2
print(ans)

Fixed submission:
M=int(input())
k,g=0,0
for i in range(M):
  d,c=map(int,input().split())
  k+=c
  g+=c*d
print((g-1)//9+(k-1))
Buggy python submission (verdict: Runtime Error):
X,Y=map(int,input().split())

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

Z=((X+Y)//3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=(comb(Z, X-Z,(10**9+7)
  print(ans)
else:
  print(0)

Fixed submission:
X,Y=map(int,input().split())

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

Z=((X+Y)//3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=(comb(Z, X-Z,(10**9+7)))
  print(ans)
else:
  print(0)

Buggy python submission (verdict: Time Limit Exceeded):
X,Y=map(int,input().split())

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

Z=((X+Y)//3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=cmb(Z, X-Z)
  print(ans%(10**9+7))
else:
  print(0)

Fixed submission:
X,Y=map(int,input().split())

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

Z=((X+Y)//3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=(comb(Z, X-Z,(10**9+7)))
  print(ans)
else:
  print(0)

Buggy python submission (verdict: Time Limit Exceeded):
X,Y=map(int,input().split())

import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

Z=((X+Y)/3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=comb(Z,(X-Z))
  print(ans%(10**9+7))
else:
  print(0)

Fixed submission:
X,Y=map(int,input().split())

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

Z=((X+Y)//3)

if (X+Y)%3==0 and abs(X-Y)<=Z:
  ans=(comb(Z, X-Z,(10**9+7)))
  print(ans)
else:
  print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
D=list(map(int,input().split()))
if D[0]==0:
  c=1
  for i in range(max(D)-1):
    c*=D.count(i+1)**D.count(i+2)
  ans=c%998244353
  print(ans)
else:
  print(0)
  

Fixed submission:
import collections


N=int(input())
D=list(map(int,input().split()))
A=collections.Counter(D)
if D[0]==0 and len(set(D))==max(D)+1 and A[0]==1:
  c=1
  for i in range(max(D)):
    c*=A[i]**A[i+1]
  ans=c%998244353  
  print(ans)
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
B=sorted(A)
G=sorted(F)[::-1]
C=[]
for i in range(N):
  C.append(B[i]*G[i])

def dfs(t):
  if t==K:
    print(max(C))
  else:
    n=C.index(max(C))
    C[n]-=G[n]
    dfs(t+1)

if sum(A) <= K:
  print(0)
else:
  dfs(0)

Fixed submission:
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
A=sorted(A)
F=sorted(F)[::-1]
import numpy as np
a=np.array(A)
f=np.array(F)

low=-1
high=10**18

while high-low>1:
  d=(high+low)//2
  #0かa-d//fの大きい値を採用するnp.maximum　
  if np.maximum(0,a-d//f).sum()<=K:
    high=d
  else:
    low=d
print(high)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
L=list(map(int,input().split()))
R=sorted(L)[::-1]

count=0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if R[k]+R[j] > R[i]:
        count+= 1
print(count)
      

Fixed submission:
import bisect
N=int(input())
L=list(map(int,input().split()))
R=sorted(L)
point=0
for i in range(N-2):
  for j in range(i+1,N-1):
    p = bisect.bisect_right(R,R[i]+R[j]-1,j+1,N)
    point+=p-(j+1)
    
print(point)