Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n = int(input())
ai = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append(s[i] + ai[i])

cnt = 0
for sj, si in itertools.combinations(s, 2):
    if si - sj == 0:
        cnt += 1

print(cnt)

Fixed submission:
import collections
import math


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


n = int(input())
ai = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append(s[i] + ai[i])

c = collections.Counter(s)
print(sum([comb(v, 2) if v > 1 else 0 for v in c.values()]))

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

s = [0]
for i in range(n):
    s.append(s[i] + ai[i])

cnt = 0
for i in range(n):
    for j in range(i, n):
        if s[j + 1] - s[i] == 0:
            cnt += 1

print(cnt)


Fixed submission:
import collections
import math


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


n = int(input())
ai = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append(s[i] + ai[i])

c = collections.Counter(s)
print(sum([comb(v, 2) if v > 1 else 0 for v in c.values()]))
Buggy python submission (verdict: Time Limit Exceeded):
def erat(n):
    l = [1 for _ in range(n)]
    i = 0
    while (i < n):
        if i == 0:
            l[i] = 0
        elif l[i] == 1:
            for j in range(i + 2, n + 1):
                if not j % (i + 1):
                    l[j - 1] = 0
            # l = list(map(lambda x: 1 if x % (i + 1) else 0, l))
        i += 1

    return l


n_max = 10**5

is_prime = erat(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1

s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])


print('plz input.')
q = int(input())
ans = []
for _ in range(q):
    li, ri = map(int, input().split())
    ans.append(s[ri] - s[li - 1])

for a in ans:
    print(a)

Fixed submission:
def get_prime_list(n):
    l = [0 for _ in range(n)]
    i = 1
    while (i < n):
        for j in range(2, int((i + 1)**0.5) + 1):
            if not (i + 1) % j:
                break
        else:
            l[i] = 1
        i += 1

    return l


n_max = 10**5
is_prime = get_prime_list(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1

s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])

q = int(input())
for _ in range(q):
    li, ri = map(int, input().split())
    print(s[ri] - s[li - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect


I = lambda: map(int, input().split())
N = int(input())
A = list(I())
B = list(I())
C = list(I())
A.sort()
B.sort()
C.sort()

summ = 0
for ai in A:
    r = bisect.bisect_right(B, ai)
    for bi in B[r:]:
        rr = bisect.bisect_right(C, bi)
        summ += (N - rr)

print(summ)

Fixed submission:
import bisect


I = lambda: map(int, input().split())
N = int(input())
A = list(I())
B = list(I())
C = list(I())
B.sort()
C.sort()

s = [0] * (N + 1)
for i, bi in enumerate(B):
    s[i + 1] = s[i] + N - bisect.bisect_right(C, bi)

print(sum(s[N] - s[bisect.bisect_right(B, ai)] for ai in A))

Buggy python submission (verdict: Runtime Error):

import bisect


I = lambda: list(map(int, input().split()))
N = I()
A = I()
B = I()
C = I()
A.sort()
B.sort()
C.sort()

summ = 0
for ai in A:
    r = bisect.bisect_right(B, ai)
    for bi in B[r:]:
        rr = bisect.bisect_right(C, bi)
        summ += (N - r) * (N - rr)

print(summ)


Fixed submission:
import bisect


I = lambda: map(int, input().split())
N = int(input())
A = list(I())
B = list(I())
C = list(I())
B.sort()
C.sort()

s = [0] * (N + 1)
for i, bi in enumerate(B):
    s[i + 1] = s[i] + N - bisect.bisect_right(C, bi)

print(sum(s[N] - s[bisect.bisect_right(B, ai)] for ai in A))
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
from operator import mul
N = int(input())
A = [int(c) for c in input().split()]
c = reduce(mul,A)
if c>10**18:
  print(-1)
else:
  print(c)


Fixed submission:
from functools import reduce
from operator import mul
N = int(input())
A = [int(c) for c in input().split()]
ans = 1
if 0 in A:
  print(0)
  import sys
  sys.exit()
for c in A:
  ans *= c
  if ans>10**18:
    print(-1)
    break
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
T = input()
s=''
for i,c in enumerate(T):
  if c=='?':
    s+='D'
  else:
    s+=c
print(s)

Fixed submission:
T = input()
print(T.replace('?','D'))
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for h in range(1,K+1):
      x = gcd(i,j)
      y = gcd(x,h)
      ans += y
print(ans)

Fixed submission:
from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for h in range(1,K+1):
      x = gcd(i,j)
      y = gcd(x,h)
      ans += y
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
S = input()
c = Counter(S)
ans = c['R']*c['G']*c['B']
for i in range(N):
  for j in range(i+1,N):
    k = j-i+j
    if k>N-1:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[i]!= S[k]:
      ans -= 1
print(ans)

Fixed submission:
from collections import Counter
N = int(input())
S = input()
c = Counter(S)
ans = c['R']*c['G']*c['B']
for i in range(N):
  for j in range(i+1,N):
    k = j-i+j
    if k>N-1:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[i]!= S[k]:
      ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
dp = [0]*(K+1)
MOD = 10**9+7
ans = 0
for X in range(K,0,-1):
  m = (K//X)**N%MOD
  x = 2*X
  while x<=K:
    m -= dp[x]
    m %= MOD
    x += X
  ans += X*m
  ans %= MOD
  dp[X] = m
print(ans)
  

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9 + 7

N, K = map(int, read().split())

A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

for d in range(K, 0, -1):
    for i in range(2, K // d + 1):
        A[d] -= A[d * i]

answer = sum(d * x for d, x in enumerate(A))
print(answer % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
for div in range(1<<(H-1)):
  ID = [0]*H
  g = 0
  for i in range(H):
    ID[i] = g
    if div>>i&1:
      g += 1
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)

Fixed submission:
H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
for div in range(1<<(H-1)):
  ID = [0]*H
  g = 0
  for i in range(H):
    ID[i] = g
    if div>>i&1:
      g += 1
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)
Buggy python submission (verdict: Runtime Error):
H,W,*L = open('0').read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
if L[0][0]=='#':
  dp[0][0] = 1
for i in range(1,H):
  if L[i][0]=='#':
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for j in range(1,W):
  if L[0][j]=='#':
    dp[0][j] = dp[0][j-1]+1
  else:
    dp[0][j] = dp[0][j-1]
for i in range(1,H):
  for j in range(1,W):
    if L[i][j]=='#':
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
print(dp[H-1][W-1])

Fixed submission:
H,W,*L = open(0).read().split()
H,W = map(int, (H,W))
dp = [[0]*W for i in range(H)]
for i in range(1,H):
  if L[i][0]!=L[i-1][0]:
    dp[i][0] = dp[i-1][0]+1
  else:
    dp[i][0] = dp[i-1][0]
for j in range(1,W):
  if L[0][j]!=L[0][j-1]:
    dp[0][j] = dp[0][j-1]+1
  else:
    dp[0][j] = dp[0][j-1]
for i in range(1,H):
  for j in range(1,W):
    if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1
    elif L[i][j]!=L[i-1][j]:
      dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1])
    elif L[i][j]!=L[i][j-1]:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1]+1)
    else:
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])
if L[0][0]=='.':
  ans = (dp[H-1][W-1]+1)//2
else:
  ans = (dp[H-1][W-1]+2)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K,*A = map(int, open(0).read().split())
Ap = []
An = []
Az = []
for c in A:
  if c>0:
    Ap.append(c)
  elif c<0:
    An.append(c)
  else:
    Az.append(c)
l = -10**20
r = 10**20
Ap.sort(reverse=True)
An.sort()
while l+1<r:
  s = (l+r)//2
  cnt = 0
  j = len(Ap)-1
  for i in range(len(Ap)):
    while j>-1 and Ap[i]*Ap[j]<s:
      j -= 1
    cnt += len(Ap)-1-j
  for i in range(len(Ap)):
    if Ap[i]*Ap[i]<s:
      cnt -= 1
  j = len(An)-1
  for i in range(len(An)):
    while j>-1 and An[i]*An[j]<s:
      j -= 1
    cnt += len(An)-1-j
  for i in range(len(An)):
    if An[i]*An[i]<s:
      cnt -= 1
  cnt //= 2
  if s>0:
    cnt += len(Az)*(len(Az)-1)//2 + len(Az)*(len(Ap)+len(An)) + len(Ap)*len(An)
  else:
    j = 0
    for i in range(len(Ap)-1,-1,-1):
      while j<len(An) and Ap[i]*An[j]<s:
        j += 1
      cnt += j
  if cnt>=K:
    r = s
  else:
    l = s
print(l)

Fixed submission:
N, K = map(int, input().split())
A = [int(c) for c in input().split()]
Ap = []
An = []
Az = []
for i in range(N):
  if A[i]>0:
    Ap += [A[i]]
  elif A[i]<0:
    An += [A[i]]
  else:
    Az += [A[i]]
lp = len(Ap)
ln = len(An)
lz = len(Az)
Ap.sort(reverse=True)
An.sort(reverse=True)
def f(m, B, C):
  cnt = 0
  j  = 0
  lb = len(B)
  lc = len(C)
  for i in range(lc):
    while j<lb:
      if B[j]*C[i]>=m:
        cnt += j
        break
      j += 1
    else:
      cnt += j
  return cnt
if K<=lp*ln:
  r = 1
  l = -10**18+10
  while l+1<r:
    n = (l+r)//2
    if f(n,Ap,An)>=K:
      r = n
    else:
      l = n
  print(l)
  import sys
  sys.exit()
K -= lp*ln
if K<=lz*(lp+ln) + lz*(lz-1)//2:
  print(0)
  import sys
  sys.exit()
K -= lz*(lp+ln) + lz*(lz-1)//2
r = 10**18+10
l = -1
while l+1<r:
  n = (l+r)//2
  P = f(n,Ap[::-1],Ap)
  for i in range(lp):
    if Ap[lp-1-i]*Ap[lp-1-i]<n:
      P -= 1
    else:
      break
  P //= 2
  N = f(n,An,An[::-1])
  for i in range(ln):
    if An[i]*An[i]<n:
      N -= 1
    else:
      break
  N //= 2
  if P+N>=K:
    r = n
  else:
    l = n
print(l)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)
N = int(input())
@lru_cache(None)
def f(n):
  if n<10:
    if n<=5:
      return n
    else:
      return 10-n+1
  p,q = divmod(n,10)
  
  return min(f(p)+q, f(p+1)+10-q)
print(f(N))

Fixed submission:
N = [int(c) for c in input()]
dp = 0,1
for i in range(len(N)):
  a = min(dp[0]+N[i], dp[1]+10-N[i])
  b = min(dp[0]+N[i]+1, dp[1]+10-N[i]-1)
  dp = a,b
print(dp[0])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
p = [int(c) for c in  input().split()]
ans = 0
for i in range(0,N-K+1,1):
  m = 0
  for j in range(K):
    m += (1+p[i+j])/2
  if m>ans:
    ans = m
print(ans)


Fixed submission:
N, K = map(int, input().split())
p = [int(c) for c in  input().split()]
ans = 0
m = 0
for i in range(K):
  m += (1+p[i])/2
ans = m
for i in range(K,N,1):
  m -= p[i-K]/2
  m += p[i]/2
  if m>ans:
    ans = m
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
ls = []
x = 0
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
  if a>x:
    x = a

L = x+H+1
dp = [10**9]*L
dp[0] = 0
for i in range(L):
  for j in range(N):
    a, b = ls[j]
    if i>=a:
      dp[i] = min(dp[i], dp[i-a]+b)

ans = min(dp[H:])

print(ans)

Fixed submission:
H, N = map(int, input().split())
ls = []
x = 0
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
  if a>x:
    x = a

L = x+H+1
dp = [10**9]*L
dp[0] = 0
for i in range(L):
  for j in range(N):
    a, b = ls[j]
    if i>=a:
      dp[i] = min(dp[i], dp[i-a]+b)

ans = min(dp[H:])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

m = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    for a in range(1, H+1):
      for b in range(1, W+1):
        if sheet[i][j]==0 or sheet[a][b]==0:
          continue
        stuck = deque([(j, i, 0)])
        while stuck:
          x, y, c = stuck.popleft()
          if x==b and y==a:
            if m<c:
              m=c
            break
          for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
              if sheet[y+dy][x+dx]==1:
                stuck += [(x+dx, y+dy, c+1)]
print(m)

Fixed submission:
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

ans = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    m = -1
    if sheet[i][j]==0:
      continue
    stuck = deque([(j, i, 0)])
    log = [[10**5]*(W+2) for i in range(H+2)]
    log[i][j] = 0
    while stuck:
      x, y, c = stuck.popleft()
      if c>m:
        m = c
      for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
        if sheet[y+dy][x+dx]==1 and log[y+dy][x+dx]>c+1:
          log[y+dy][x+dx] = c+1
          stuck += [(x+dx, y+dy, c+1)]
    if ans<m:
      ans = m
print(ans)
Buggy python submission (verdict: Runtime Error):
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 )

N, K = map(int, input().split())
a = [int(c) for c in input().split()]
a.sort()
M = 0
m = 0
for i in range(N-1, 0, -1):
  M += cmb(i,K-1, mod)*a[i]
  M %= mod
for i in range(N-1):
  m += cmb(N-1-i, K-1, mod)*a[i]
  m %= mod
print((M-m)%mod)

Fixed submission:
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
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 )

N, K = map(int, input().split())
a = [int(c) for c in input().split()]
a.sort()
M = 0
m = 0
for i in range(N-1, 0, -1):
  M += cmb(i,K-1, mod)*a[i]
  M %= mod
for i in range(N-1):
  m += cmb(N-1-i, K-1, mod)*a[i]
  m %= mod
print((M-m)%mod)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
N, M = map(int, input().split())
a = [int(c) for c in input().split()]
G = a[0]*a[1]//gcd(a[0], a[1])
g = (a[0]//2)*(a[1]//2)//gcd(a[0]//2, a[1]//2)
for i in range(2,N):
  G = G*a[i]//gcd(G, a[i])
  g = g*(a[i]//2)//gcd(g, a[i]//2)
if M<g:
  print(0)
elif g%2==0:
  print(0)
else:
  n = (M-g)//G
  print(n+1)


Fixed submission:
from fractions import gcd
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

N, M = map(int, input().split())
a = [int(c) for c in input().split()]
b = [c//2 for c in a]
g = reduce(lcm_base, b, 1)
G = reduce(lcm_base, a, 1)
if M<g:
  print(0)
  import sys
  sys.exit()
m = a[0]&-a[0]
for i in range(N):
  if m != a[i]&(-a[i]):
    print(0)
    break
else:
  n = (M-g)//G
  print(n+1)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
N, M = map(int, input().split())
a = [int(c) for c in input().split()]
b = [c//2 for c in a]
g = b[0]*b[1]//gcd(b[0], b[1])
for i in range(2,N):
  g = g*b[i]//gcd(g, b[i])

G = a[0]*a[1]//gcd(a[0], a[1])
for i in range(2,N):
  G = G*a[i]//gcd(G, a[i])

if M<g:
  print(0)
else:
  n = (M-g)//G
  print(n+1)


Fixed submission:
from fractions import gcd
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

N, M = map(int, input().split())
a = [int(c) for c in input().split()]
b = [c//2 for c in a]
g = reduce(lcm_base, b, 1)
G = reduce(lcm_base, a, 1)
if M<g:
  print(0)
  import sys
  sys.exit()
m = a[0]&-a[0]
for i in range(N):
  if m != a[i]&(-a[i]):
    print(0)
    break
else:
  n = (M-g)//G
  print(n+1)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N,M,*A = map(int, open('0').read().split())
A = np.sort(A)
B = np.cumsum(np.concatenate([[0],A[::-1]]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = np.sum(N-np.searchsorted(A,s-A))
  if cnt>=M:
    l = s
  else:
    r = s
ind = np.searchsorted(A,r-A)
M -= np.sum(N-ind)
ans = np.sum(B[N-ind]+A*(N-ind))+M*l
print(ans)


Fixed submission:
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>l:
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
      break
    j += 1
ans += (M-m)*l
print(ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open('0').read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**9
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

Fixed submission:
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>l:
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
      break
    j += 1
ans += (M-m)*l
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N%2==1:
  print(0)
else:
  ans = 0
  m = 5
  n = 1
  while m<=N:
    c = N//m
    c = c//2
    ans += c
    m *= 5
print(ans)

Fixed submission:
N = int(input())

if N%2==1:
  print(0)
else:
  ans = 0
  m = 5
  n = 1
  while m<=N:
    c = N//m
    c = c//2
    ans += c
    m *= 5
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
MOD = 10**9+7
a = [int(c) for c in input().split()]
ls = [0]*60
for i in range(N):
  m = a[i]
  for j in range(60):
    if m%2==1:
      ls[j] += 1
    m >>= 1

ans = 0
x = 1
for i in range(60):
  ans += x*(ls[i]*(N-ls[i]))
  ans %= MOD
  x *= 2
  x %= MOD
print(ans)

Fixed submission:
N = int(input())
MOD = 10**9+7
a = [int(c) for c in input().split()]
M = max(a).bit_length()
ls = [0]*M
for i in range(N):
  m = a[i]
  for j in range(M):
    if m%2==1:
      ls[j] += 1
    m >>= 1

ans = 0
x = 1
for i in range(M):
  ans += x*(ls[i]*(N-ls[i]))
  ans %= MOD
  x *= 2
  x %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_left
N, K = map(int, input().split())
a = [int(c)-1 for c in input().split()]
s = [0]
for i in range(N):
  s += [(s[-1]+a[i])%K]
dic = defaultdict(list)

for i in range(N+1):
  dic[s[i]] += [i]

ans = 0
for k in dic.keys():
  ls = dic[k]
  for j in range(len(ls)):
    ind = bisect_left(ls, ls[j]-K+2)
    ans += j-ind
    if ind>0 and ls[ind-1]+1 == ls[ind]:
      ans += 1
    elif ind<ls[0]:
      ans += 1
#  print(k, ans)

print(ans)

Fixed submission:
from collections import defaultdict
import itertools

N, K = map(int, input().split())
A = [int(c)-1 for c in input().split()]
A = [0] + A
Acum = list(itertools.accumulate(A))
Acum = [x%K for x in Acum]

counter = defaultdict(int)

ans = 0
for i,x in enumerate(Acum):
  ans += counter[x]
  counter[x] += 1
  if i>=K-1:
    counter[Acum[i-K+1]] -= 1
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_left
N, K = map(int, input().split())
a = [int(c)-1 for c in input().split()]
s = [0]
for i in range(N):
  s += [(s[-1]+a[i])%K]
dic = defaultdict(list)

for i in range(N+1):
  dic[s[i]] += [i]

ans = 0
for k in dic.keys():
  ls = dic[k]
  for j in range(len(ls)):
    ind = bisect_left(ls, ls[j]-K+2)
    ans += j-ind
    if ind>0 and ls[ind-1]+1 == ls[ind]:
      ans += 1
#  print(k, ans)

print(ans)

Fixed submission:
from collections import defaultdict
import itertools

N, K = map(int, input().split())
A = [int(c)-1 for c in input().split()]
A = [0] + A
Acum = list(itertools.accumulate(A))
Acum = [x%K for x in Acum]

counter = defaultdict(int)

ans = 0
for i,x in enumerate(Acum):
  ans += counter[x]
  counter[x] += 1
  if i>=K-1:
    counter[Acum[i-K+1]] -= 1
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_left
N, K = map(int, input().split())
a = [int(c)-1 for c in input().split()]
s = [0]
for i in range(N):
  s += [(s[-1]+a[i])%K]
dic = defaultdict(list)

for i in range(N+1):
  dic[s[i]] += [i]

ans = 0
for k in dic.keys():
  ls = dic[k]
  for j in range(len(ls)):
    ind = bisect_left(ls, ls[j]-K+2)
    ans += j-ind
    if ind!=0 and ls[ind-1]+1 == ls[ind]:
      ans += 1
#  print(k, ans)

print(ans)

Fixed submission:
from collections import defaultdict
import itertools

N, K = map(int, input().split())
A = [int(c)-1 for c in input().split()]
A = [0] + A
Acum = list(itertools.accumulate(A))
Acum = [x%K for x in Acum]

counter = defaultdict(int)

ans = 0
for i,x in enumerate(Acum):
  ans += counter[x]
  counter[x] += 1
  if i>=K-1:
    counter[Acum[i-K+1]] -= 1
print(ans)