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

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "#": continue
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "#": continue
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      if (h, w) in used: continue
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from copy import deepcopy

H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
maxc = 0

for h in range(H):
  for w in range(W):
    if M[h][w] == "#": continue
    m = deepcopy(M)
    q = deque([(h, w, 0)])
    while q:
      h, w, c = q.popleft()
      maxc = max(maxc, c)
      if 0 <= h-1 and m[h-1][w] == ".": q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == ".": q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == ".": q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == ".": q.append((h, w+1, c+1))
      m[h][w] = "#"
print(maxc)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "#": continue
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      if (h, w) in used: continue
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = input()
l = {}
a = [set() for i in range(N)]
a[-1].add(s[-1])

for i in range(N-2, -1 , -1):
  a[i] = a[i+1] | {s[i]} 

for i1 in range(N-2):
  for i2 in range(i1+1, N-1):
    l[s[i1] + s[i2]] = l.get(s[i1] + s[i2], set()) | a[i2+1]

r = 0
for i in l.values():
  r += len(i)
print(r)

Fixed submission:
N = int(input())
s = input()
l = {}
a = [{} for i in range(N)]
a[-1] = {s[-1]: N-1}

for i in range(N-2, -1 , -1):
  a[i] = a[i+1].copy()
  a[i].update({s[i]: i})

r = 0
for k1, v1 in a[0].items():
  if v1 >= N - 2: continue
  for k2, v2 in a[v1+1].items():
    if v2 >= N - 1 : continue
    r += len(a[v2+1].keys())

print(r)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = input()
l = set()
for i1 in range(N):
  for i2 in range(i1+1, N):
    for i3 in range(i2+1, N):
      l.add(s[i1] + s[i2] + s[i3])
print(len(l))

Fixed submission:
N = int(input())
s = input()
l = {}
a = [{} for i in range(N)]
a[-1] = {s[-1]: N-1}

for i in range(N-2, -1 , -1):
  a[i] = a[i+1].copy()
  a[i].update({s[i]: i})

r = 0
for k1, v1 in a[0].items():
  if v1 >= N - 2: continue
  for k2, v2 in a[v1+1].items():
    if v2 >= N - 1 : continue
    r += len(a[v2+1].keys())

print(r)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]

abd = {}
for a, b in ab:
  abd[a] = abd.get(a,set())
  abd[a].add(len(abd[a]) + 1)
  
  abd[b] = abd.get(b,set())
  abd[b].add(len(abd[b]) + 1)

rk = max([len(x) for x in abd.values()])
print(rk)

for a, b in ab:
  c = abd[a].pop()
  abd[b].remove(c)
  print(c)

Fixed submission:
from collections import deque

N = int(input())
edge = [set() for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a].add((b, i))
  edge[b].add((a, i))

r = [0] * (N - 1)
q = deque([(0, 1)])

while q:
  preC, fromv = q.popleft()
  c = 0
  for tov, i in edge[fromv]:
    edge[tov].remove((fromv, i))
    c += 1 + (c + 1 == preC)
    q.append((c, tov))
    r[i] = c
print(max(r))
for x in r:
  print(x)
Buggy python submission (verdict: Runtime Error):
M = int(input())
CD = C = 0
for i in range(M):
  d, c = map(int, input().split())
  CD += c * d
  C += c
print(C - 1 + (CD - 1) // 9)


Fixed submission:
X, Y = map(int, input().split())
r = 0
if(X == 1):
  r += 300000
elif(X == 2):
  r += 200000
elif(X == 3):
  r += 100000
else:
  pass

if(Y == 1):
  r += 300000
elif(Y == 2):
  r += 200000
elif(Y == 3):
  r += 100000
else:
  pass

if(X == Y == 1):
  r += 400000

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
l = sorted(list(map(int, input().split())))

result = 0

for i in range(N):
  for j in range(i + 1, N):
    for k in range(j + 1, N):
      if(l[i] + l[j] > l[k]):
        result += 1
      else:
        break
        

print(result)

Fixed submission:
import bisect

N = int(input())
l = sorted(list(map(int, input().split())))

result = 0

for i in range(N):
  for j in range(i + 1, N):
    cur = bisect.bisect_left(l, l[i] + l[j]) - j - 1
    result += cur if cur > 0 else 0   

print(result)

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

result = 0

for i in range(N):
  for j in range(i + 1, N):
    for k in range(j + 1, N):
      if(l[i] + l[j] > l[k]):
        result += 1
      else:
        break
        

print(result)

Fixed submission:
import bisect

N = int(input())
l = sorted(list(map(int, input().split())))

result = 0

for i in range(N):
  for j in range(i + 1, N):
    cur = bisect.bisect_left(l, l[i] + l[j]) - j - 1
    result += cur if cur > 0 else 0   

print(result)
Buggy python submission (verdict: Runtime Error):
from math import factorial

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

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

for i in range(1, K + 1):
  print((cmb(N - K + 1, i) * cmb(K - 1, i - 1)) % (10 ** 9 + 7))

Fixed submission:
from math import factorial

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

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

for i in range(1, K + 1):
  try:
    print((cmb(N - K + 1, i) * cmb(K - 1, i - 1)) % (10 ** 9 + 7))
  except:
    print(0)
Buggy python submission (verdict: Runtime Error):
class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

  def same(self, x, y):
    return self.root(x) == self.root(y)

N, M = map(int, input().split())
uf = UnionFind(N)

for i in range(M):
  x, y, z = map(int, input().split())
  uf.unite(x-1, y-1)

ans = set()
for i in range(N):
  ans.add(uf.root(i))
print(len(ans))

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

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

  def same(self, x, y):
    return self.root(x) == self.root(y)

N, M = map(int, input().split())
uf = UnionFind(N)

for i in range(M):
  x, y, z = map(int, input().split())
  uf.unite(x-1, y-1)

ans = set()
for i in range(N):
  ans.add(uf.root(i))
print(len(ans))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque([(h, w, 0) for w in range(W) for h in range(H) if m[h][w] == "#"])
ql = q.popleft
qa = q.append

while q:
  h, w, c = ql()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      qa((h+dh, w+dw, c+1))

print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "#":
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      q.append((h+dh, w+dw, c+1))

print(ans)

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

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "#":
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      q.append((h+dh, w+dw, c+1))

print(ans)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "#":
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      q.append((h+dh, w+dw, c+1))

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

def runLength(s):
  if len(s) == 0: return []
  if len(s) == 1: return [(s, 1)]
  res = []
  lc = 1
  for i in range(1, len(s)):
    if s[i-1] == s[i]:
      lc += 1
    else:
      res.append((s[i-1], lc))
      lc = 1
  res.append((s[i], lc))
  return res

S = runLength(input())
accsum = [0] * (1 + (S[0][0] == "0"))
for i in range(len(S)):
  accsum.append(accsum[-1] + S[i][1])
if S[-1][0] == "0":
  accsum.append(accsum[-1])
print(max([accsum[i] - accsum[i-2*K-1] for i in range(2*K+1, len(accsum), 2)]) if N >= 2*K else N)

Fixed submission:
N, K = map(int, input().split())

def runLength(s):
  if len(s) == 0: return []
  if len(s) == 1: return [(s, 1)]
  res = []
  lc = 1
  for i in range(1, len(s)):
    if s[i-1] == s[i]:
      lc += 1
    else:
      res.append((s[i-1], lc))
      lc = 1
  res.append((s[i], lc))
  return res

S = runLength(input())
accsum = [0] * (1 + (S[0][0] == "0"))
for i in range(len(S)):
  accsum.append(accsum[-1] + S[i][1])
if S[-1][0] == "0":
  accsum.append(accsum[-1])
print(max([accsum[i] - accsum[i-2*K-1] for i in range(2*K+1, len(accsum), 2)]) if len(accsum) > 2*K+2 else N)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
s = input()
AClist = []

for i in range(N - 1):
  if(s[i:i + 2] == "AC"): AClist.append(i)

for i in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  result = 0
  idx = 0
  
  while(idx < len(AClist) and l > AClist[idx]):
    idx += 1
    
  while(idx < len(AClist) and AClist[idx] + 1 <= r):
    idx += 1
    result += 1
  
  print(result)

Fixed submission:
N, Q = map(int, input().split())
s = input()
AClist = [0] * N

for i in range(N - 1):
  AClist[i + 1] = AClist[i] + int(s[i:i + 2] == "AC")
  
for i in range(Q):
  l, r = map(int, input().split())
  print(AClist[r - 1] - AClist[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
s = input()
AClist = []

for i in range(Q):
  l, r = map(int, input().split())
  result = 0
  for j in range(l - 1, r - 1):
    if(s[j:j + 2] == "AC"): result += 1
  print(result)

Fixed submission:
N, Q = map(int, input().split())
s = input()
AClist = [0] * N

for i in range(N - 1):
  AClist[i + 1] = AClist[i] + int(s[i:i + 2] == "AC")
  
for i in range(Q):
  l, r = map(int, input().split())
  print(AClist[r - 1] - AClist[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
  for k in range(1,K+1):
    if i + k < N:
      dp[i+k] = min(dp[i+k], dp[i] + abs(h[i+k] - h[i]))

print(dp[-1])

Fixed submission:
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
  for k in range(1,K+1):
    if i + k < N:
      dp[i+k] = min(dp[i+k], dp[i] + abs(h[i+k] - h[i]))

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
dp = [[float("inf")] * (10**5 + 1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w) if j >= v and dp[i][j-v] + w <= W else dp[i][j]

ans = 0
for i in range(10**5 + 1):
  if dp[-1][i] <= W:
    ans = i
print(ans)

Fixed submission:
N, W = map(int, input().split())
dp = [[float("inf")] * (10**5 + 1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w) if j >= v and dp[i][j-v] + w <= W else dp[i][j]

ans = 0
for i in range(10**5 + 1):
  if dp[-1][i] <= W:
    ans = i
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
edge = [[] for i in range(N)]
for i in range(M):
  x, y = map(int, input().split())
  edge[x-1].append(y-1)

dp = [-1] * N
def dist(v):
  if dp[v] != -1: return dp[v]
  
  res = 0
  for to in edge[v]:
    res = max(res, dist(to) + 1)
  
  dp[v] = res
  return res

ans = 0
for i in range(N):
  ans = max(ans, dist(i))

print(ans)

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

N, M = map(int, input().split())
edge = [[] for i in range(N)]
for i in range(M):
  x, y = map(int, input().split())
  edge[x-1].append(y-1)

dp = [-1] * N
def dist(v):
  if dp[v] != -1: return dp[v]
  
  res = 0
  for to in edge[v]:
    res = max(res, dist(to) + 1)
  
  dp[v] = res
  return res

ans = 0
for i in range(N):
  ans = max(ans, dist(i))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))

dp = [[0] * (N+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
  for j in range(i+1):
    dp[i][j] = dp[i-1][j] * (1 - P[i-1]) + (dp[i-1][j-1] if j > 0 else 0) * P[i-1]
print(sum(dp[N][N//2+1:]))

Fixed submission:
N = int(input())
P = list(map(float, input().split()))

dp = [[0] * (N+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
  for j in range(i+1):
    dp[i][j] = dp[i-1][j] * (1 - P[i-1]) + (dp[i-1][j-1] if j > 0 else 0) * P[i-1]
print(sum(dp[N][N//2+1:]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2**20)

N = int(input())
A = list(map(int, input().split()))

dp = [[[-1] * (N+1) for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 0

S = [0] * 3
for a in A:
  S[a-1] += 1

def calc(i, j, k):
  if dp[i][j][k] >= 0: return dp[i][j][k]
  dp[i][j][k] = (i * (calc(i-1, j, k) if i > 0 else 0) + j * (calc(i+1, j-1, k) if j > 0 else 0) + k * (calc(i, j+1, k-1) if k > 0 else 0) + N) / (i + j + k)
  return dp[i][j][k]

print(calc(*S))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2**20)

N = int(input())
A = list(map(int, input().split()))

dp = [[[-1] * (N+1) for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 0

S = [0] * 3
for a in A:
  S[a-1] += 1

def calc(i, j, k):
  if dp[i][j][k] >= 0: return dp[i][j][k]
  dp[i][j][k] = (i * (calc(i-1, j, k) if i > 0 else 0) + j * (calc(i+1, j-1, k) if j > 0 else 0) + k * (calc(i, j+1, k-1) if k > 0 else 0) + N) / (i + j + k)
  return dp[i][j][k]

print(calc(*S))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])

Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1

@lru_cache(maxsize=None)
def calc(i, j, k):
  if i==j==k==0: return 0
  return (i * (calc(i-1, j, k) if i > 0 else 0) + j * (calc(i+1, j-1, k) if j > 0 else 0) + k * (calc(i, j+1, k-1) if k > 0 else 0) + N) / (i + j + k)

print(calc(*S))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
cy = [1] * M
city = []

for i in range(M):
  p, y = map(int, input().split())
  city.append((y, p, i))
city.sort()

ans = [""] * M

for y, p, i in city:
  ans[i] = ("000000" + str(p))[-6:] + ("000000" + str(cy[p-1]))[-6:]
  cy[p-1] += 1

print(*ans, sep="\n")

Fixed submission:
N, M = map(int, input().split())
cy = [1] * N
city = []

for i in range(M):
  p, y = map(int, input().split())
  city.append((y, p, i))
city.sort()

ans = [""] * M

for y, p, i in city:
  ans[i] = ("000000" + str(p))[-6:] + ("000000" + str(cy[p-1]))[-6:]
  cy[p-1] += 1

print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+33):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
while(M > 1):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
r = 1
for v in primes.values():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)

Fixed submission:
N, M = map(int, input().split())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+33):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
while(M > 1):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
r = 1
for v in primes.values():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)

Buggy python submission (verdict: Runtime Error):
N = int(input())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+34):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
n = N
while(n > 1):
  if(n % i == 0):
    primes[i] = primes.get(i, 0) + 1
    n //= i
  else:
    i += 2 - (n + 1) % 2

r = 1
for v in primes.value():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)

Fixed submission:
N, M = map(int, input().split())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+33):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
while(M > 1):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
r = 1
for v in primes.values():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())
city = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  l, r = map(int, input().split())
  city[l][r] += 1

for i in range(N+1):
  for j in range(N):
    city[i][j+1] += city[i][j]

for i in range(Q):
  p, q = map(int, input().split())
  print(sum([city[j][q] - city[j][p-1] for j in range(p, q+1)]))

Fixed submission:
N, M, Q = map(int, input().split())
city = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  l, r = map(int, input().split())
  city[l][r] += 1

for i in range(N+1):
  for j in range(N):
    city[i][j+1] += city[i][j]

for i in range(N+1):
  for j in range(N):
    city[j+1][i] += city[j][i]

for i in range(Q):
  p, q = map(int, input().split())
  print(city[q][q] - city[p-1][q] - city[q][p-1] + city[p-1][p-1])
Buggy python submission (verdict: Runtime Error):
r = int(input());print("ABC"if r<1200else"ARC"if else r<2800else"AGC")

Fixed submission:
r = int(input())
print("ABC" if r<1200 else "ARC" if r<2800 else "AGC")
Buggy python submission (verdict: Runtime Error):
s = list(input())
if(len(s) > 9):
  print("NO")
  exit()

ans = "AKIHABARA"
i = 0

while(i < len(ans) and len(s) <= len(ans)):
  if("".join(s) == ans):
    print("YES")
    exit()
  
  if(i == len(ans) - 1 or s[i] != ans[i]):
    s.insert(i, "A")
  else:
    i += 1

print("NO")

Fixed submission:
import re
print("YES" if re.match("^A?KIHA?BA?RA?$", input()) else "NO")

Buggy python submission (verdict: Runtime Error):
s = list(input())
if(len(s) > 10):
  print("NO")
  exit()

ans = "AKIHABARA"
i = 0

while(i < len(ans) and len(s) <= len(ans)):
  if("".join(s) == ans):
    print("YES")
    exit()
  
  if(i == len(ans) - 1 or s[i] != ans[i]):
    s.insert(i, "A")
  else:
    i += 1

print("NO")

Fixed submission:
import re
print("YES" if re.match("^A?KIHA?BA?RA?$", input()) else "NO")
Buggy python submission (verdict: Runtime Error):
n,a=map(int,input().split())
print(n*n-a)

Fixed submission:
print(int(input())**2-int(input()))
Buggy python submission (verdict: Runtime Error):
n, k = map(int,input().split())
result = float("Inf")
length = 0
for i in range(N):
  a, b = map(int,input().split())
  if(length < k):
    length += b
    result = max(result, a)
  else:
    if(a < result):
      length += b
      if(length > k):
        result = a
print(result)

Fixed submission:
import heapq
n, k = map(int,input().split())
hq = []
for i in range(n):
  heapq.heappush(hq, tuple(map(int, input().split())))
length = 0
while(length < k):
  a, b = heapq.heappop(hq)
  length += b
print(a)