Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
if m%2:
  print(-1)
else:
  G = [[] for _ in range(n+1)]
  par = [-1]*(n+1)
  ch = [[] for _ in range(n+1)]
  seen = [False]*(n+1)
  used = set()
  C = [0]*(n+1)
  for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
  
  stack = [1]
  seen[1] = True
  while stack:
    v = stack.pop()
    for nv in G[v]:
      if seen[nv]:
        if par[v] != nv:
          if (min(v, nv), max(v, nv)) not in used:
            used.add((min(v, nv), max(v, nv)))
            print(v, nv)
            C[v] ^= 1
      else:
        seen[nv] = True
        par[nv] = v
        ch[v].append(nv)
        stack.append(nv)
  
  def bottom_up(v):
    for nv in ch[v]:
      bottom_up(nv)
    if v == 1:
      return
    if C[v]:
      C[v] ^= 1
      print(v, par[v])
    else:
      C[par[v]] ^= 1
      print(par[v], v)
      
  bottom_up(1)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
if m%2:
  print(-1)
else:
  G = [[] for _ in range(n+1)]
  par = [-1]*(n+1)
  ch = [[] for _ in range(n+1)]
  seen = [False]*(n+1)
  used = set()
  C = [0]*(n+1)
  for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
  
  stack = [1]
  seen[1] = True
  while stack:
    v = stack.pop()
    for nv in G[v]:
      if seen[nv]:
        if par[v] != nv:
          if (min(v, nv), max(v, nv)) not in used:
            used.add((min(v, nv), max(v, nv)))
            print(v, nv)
            C[v] ^= 1
      else:
        seen[nv] = True
        par[nv] = v
        ch[v].append(nv)
        stack.append(nv)
  
  def bottom_up(v):
    for nv in ch[v]:
      bottom_up(nv)
    if v == 1:
      return
    if C[v]:
      C[v] ^= 1
      print(v, par[v])
    else:
      C[par[v]] ^= 1
      print(par[v], v)
      
  bottom_up(1)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split()),print(min(a*b,c))

Fixed submission:
a,b,c=map(int,input().split());print(min(a*b,c))
Buggy python submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
F = [set() for _ in range(n)]
G = np.zeros((n, n))
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  F[u].add(v)
for i in range(n):
  for j in F[i]:
    for k in F[j]:
      for l in F[k]:
        G[i][l] = 1
csr = csr_matrix(G)
s, t = map(int, input().split())
s -= 1
t -= 1
A = dijkstra(csr, indices=s)
if A[t] == float("inf"):
  print(-1)
else:
  print(int(A[t]))

Fixed submission:
from collections import deque

n, m = map(int, input().split())
F = [set() for _ in range(3*n)]
for _ in range(m):
  u, v = map(int, input().split())
  u = (u-1)*3
  v = (v-1)*3
  F[u].add(v+1)
  F[u+1].add(v+2)
  F[u+2].add(v)
s, t = map(int, input().split())
s = (s-1)*3
t = (t-1)*3
dist = [-1]*(3*n)
dist[s] = 0
dq = deque([s])
while dq:
  v = dq.popleft()
  for nv in F[v]:
    if dist[nv] != -1:
      continue
    dist[nv] = dist[v]+1
    dq.append(nv)
    if nv == t:
      break
  else:
    continue
  break
print(dist[t]//3)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7
  
n, k = map(int, input().split())
S = set()
i = 1
while i * i <= n:
  S.add(i)
  S.add(n//i)
  i += 1
L = [0] + sorted(S)
l = len(L) - 1
num = [0]*l
for i in range(l):
  num[i] = L[i+1] - L[i]
dp = [0]*l
dp[0] = 1
for _ in range(k):
  A = list(accumulate(dp))
  for i in range(l):
    dp[i] = A[l-1-i] * num[i]
    dp[i] %= MOD
ans = sum(dp) % MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7
  
n, k = map(int, input().split())
S = set()
i = 1
while i * i <= n:
  S.add(i)
  S.add(n//i)
  i += 1
L = [0] + sorted(S)
l = len(L) - 1
num = [0]*l
for i in range(l):
  num[i] = L[i+1] - L[i]
dp = [0]*l
dp[0] = 1
for _ in range(k):
  A = list(accumulate(dp))
  for i in range(l):
    dp[i] = A[l-1-i] * num[i]
    dp[i] %= MOD
ans = sum(dp) % MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
P = [[-1]*(k+1) for _ in range(n+1)]
MOD = 10**9+7

def product(l, k):
  if P[l][k] != -1:
    return P[l][k]
  if k==1:
    return l
  c = 0
  for i in range(1, l+1):
    c += product(n//i, k-1)
    c %= MOD
  P[l][k] = c
  return c

print(product(n, k))

Fixed submission:
import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7
  
n, k = map(int, input().split())
S = set()
i = 1
while i * i <= n:
  S.add(i)
  S.add(n//i)
  i += 1
L = [0] + sorted(S)
l = len(L) - 1
num = [0]*l
for i in range(l):
  num[i] = L[i+1] - L[i]
dp = [0]*l
dp[0] = 1
for _ in range(k):
  A = list(accumulate(dp))
  for i in range(l):
    dp[i] = A[l-1-i] * num[i]
    dp[i] %= MOD
ans = sum(dp) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i == 0 or j == 0:
      dp[i][j] = 1
    else:
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
      if S[i-1] == T[j-1]:
        dp[i][j] += dp[i-1][j-1]
      dp[i][j] %= MOD
ans = dp[n][m]
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i == 0 or j == 0:
      dp[i][j] = 1
    else:
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
      if S[i-1] == T[j-1]:
        dp[i][j] += dp[i-1][j-1]
      dp[i][j] %= MOD
ans = dp[n][m]
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
XY = tuple(tuple(map(int, input().split())) for _ in range(n))
L = []
for i in range(n-1):
  for j in range(i+1, n):
    x1, y1 = XY[i]
    x2, y2 = XY[j]
    L.append((x1-x2, y1-y2))
    L.append((x2-x1, y2-y1))
C = Counter(L)
ans = n - C.most_common()[0][1]
print(ans)

Fixed submission:
from collections import Counter
n = int(input())
if n == 1:
  print(1)
else:
  XY = tuple(tuple(map(int, input().split())) for _ in range(n))
  L = []
  for i in range(n-1):
    for j in range(i+1, n):
      x1, y1 = XY[i]
      x2, y2 = XY[j]
      L.append((x1-x2, y1-y2))
      L.append((x2-x1, y2-y1))
  C = Counter(L)
  ans = n - C.most_common()[0][1]
  print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
w = sorted(list(map(int, input().split())))
c = float("inf")
for i in range(n-1):
  c = min(c, abs(w[:i+1] - w[i+1:n]))
print(c)

Fixed submission:
n = int(input())
W = list(map(int, input().split()))
c = float("inf")
for i in range(n-1):
  d = abs(sum(W[:i+1]) - sum(W[i+1:]))
  c = min(c, d)
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [ int(input()) for _ in range(m) ]
dp = [0]*n
for i in range(n):
  if not i+1 in a:
    if i == 0:
      dp[i] = 1
    elif i == 1:
      dp[i] = 1 + dp[i-1]
    else:
      dp[i] = dp[i-2] + dp[i-1]
  if dp[i] >= 1000000007:
    dp[i] %= 1000000007
print(dp[n-1]%1000000007)

Fixed submission:
n, m = map(int, input().split())
A = [ int(input()) for _ in range(m) ]
dp = [0]*(n+1)
broken = [False]*(n+1)
for i in A:
  broken[i] = True
dp[0] = 1
if not broken[1]:
  dp[1] = 1
for i in range(2, n+1):
  if broken[i]:
    continue
  else:
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n]%(10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [ int(input()) for _ in range(m) ]
dp = [0]*n
for i in range(n):
  if not i+1 in a:
    if i == 0:
      dp[i] = 1
    elif i == 1:
      dp[i] = 1 + dp[i-1]
    else:
      dp[i] = dp[i-2] + dp[i-1]
print(dp[n-1]%1000000007)

Fixed submission:
n, m = map(int, input().split())
A = [ int(input()) for _ in range(m) ]
dp = [0]*(n+1)
broken = [False]*(n+1)
for i in A:
  broken[i] = True
dp[0] = 1
if not broken[1]:
  dp[1] = 1
for i in range(2, n+1):
  if broken[i]:
    continue
  else:
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n]%(10**9+7))

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = [ int(input()) for _ in range(m) ]
dp = [0]*n
if not 1 in a:
  dp[0] = 1
if not 2 in a:
  dp[1] = 1 + dp[0]
for i in range(2, n):
  if i+1 in a:
    dp[i] = 0
  else:
    dp[i] = dp[i-2] + dp[i-1]
print(dp[n-1]%1000000007)

Fixed submission:
n, m = map(int, input().split())
A = [ int(input()) for _ in range(m) ]
dp = [0]*(n+1)
broken = [False]*(n+1)
for i in A:
  broken[i] = True
dp[0] = 1
if not broken[1]:
  dp[1] = 1
for i in range(2, n+1):
  if broken[i]:
    continue
  else:
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n]%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
ans = 0
while "ABC" in s:
  ans += s.count("ABC")
  s = s.replace("ABC", "BCA")
print(ans)

Fixed submission:
import re

s = input()
ans = 0
s = s.replace("BC", "D")
L = re.split('[BC]', s)
for i in L:
  k = len(i)
  temp = 0
  for j in range(k):
    if i[k-1-j] == "D":
      temp += 1
    else:
      ans += temp
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
ans = 0
while "ABC" in s:
  ans += s.count("ABC")
  s = s.replace("ABC", "BCA")
print(ans)

Fixed submission:
import re

s = input()
ans = 0
s = s.replace("BC", "D")
L = re.split('[BC]', s)
for i in L:
  k = len(i)
  temp = 0
  for j in range(k):
    if i[k-1-j] == "D":
      temp += 1
    else:
      ans += temp
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()), reverse=True)
print(sum(C[1:]))
L = [-1]*n
L[0] = C[0]
L[T[0][0]] = C[1]
used = [0, T[0][0]]
for i in range(2, n):
  for v in used:
    for nv in T[v]:
      if L[nv] == -1:
        L[nv] = C[i]
        used.append(nv)
        break
    else:
      continue
    break
print(*L)

Fixed submission:
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()))
print(sum(C[:-1]))
L = [-1]*n
stack = [0]
while stack:
  temp = stack.pop()
  L[temp] = C.pop()
  for v in T[temp]:
    if L[v] == -1:
      stack.append(v)
print(*L)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()), reverse=True)
print(sum(C[1:]))
L = [-1]*n
L[0] = C[0]
L[T[0][0]] = C[1]
used = [0, T[0][0]]
for i in range(2, n):
  for v in used:
    for nv in T[v]:
      if L[nv] == -1:
        L[nv] = C[i]
        used.append(nv)
        break
    else:
      continue
    break
print(*L)

Fixed submission:
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()))
print(sum(C[:-1]))
L = [-1]*n
stack = [0]
while stack:
  temp = stack.pop()
  L[temp] = C.pop()
  for v in T[temp]:
    if L[v] == -1:
      stack.append(v)
print(*L)
Buggy python submission (verdict: Time Limit Exceeded):
U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)

Fixed submission:
U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)

Fixed submission:
U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
read = sys.stdin.read

def main():
  n, q = map(int, input().split())
  event = []
  stop = set()
  for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))
  event.sort()
  event.append((float("inf"), 0, 0))
  D = list(map(int, read().split()))
  now = 0
  for t, b, x in event:
    while t > D[now]:
      if stop:
        print(min(stop))
      else:
        print(-1)
      now += 1
      if now == q:
        exit()
    if b == 1:
      stop.add(x)
    else:
      stop.remove(x)
      
if __name__ == "__main__":
  main()

Fixed submission:
a, p = map(int, input().split())
print((3*a+p)//2)
Buggy python submission (verdict: Runtime Error):
n, k =map(int,input().split())
s = input()
x = s[k-1]
if x == "A":
  s[k-1] = "a"
elif x == "B":
  s[k-1] = "b"
else:
  s[k-1] = "c"
print(s)

Fixed submission:
n, k =map(int,input().split())
s = input()
x = s[k-1]
if x == "A":
  t = s[:k-1] + "a" + s[k:]
elif x == "B":
  t = s[:k-1] + "b" + s[k:]
else:
  t = s[:k-1] + "c" + s[k:]
print(t)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

def s_gcd(numbers):
  return reduce(gcd, numbers)

n = int(input())
A = list(map(int, input().split()))
c = 1
for i in range(n):
  g = s_gcd(A[:i] + A[i+1:])
  c = max(c, g)
  
print(c)

Fixed submission:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
L = [1]*n
R = [1]*n
L[0] = A[0]
R[n-1] = A[n-1]
for i in range(1, n):
  L[i] = gcd(L[i-1], A[i])
  R[n-i-1] = gcd(R[n-i], A[n-i-1])
m = 1
for i in range(n-2):
  m = max(m, gcd(L[i], R[i+2]))
print(max(L[n-2], m, R[1]))
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = tuple(int(input()) for _ in range(n))
S = sum(A)
mod = 998244353
ans = pow(3, n, mod) - (pow(2, n, mod)-2)*3 - 3
cnt = 0
dp = [[[0]*(S+1) for j in range(n+2)] for i in range(n+1)]
dp[0][0][0] = 1
for i, a in enumerate(A):
  for j in range(i+2):
    for k in range(S+1):
      if k >= a and j:
        dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-a]
      else:
        dp[i+1][j][k] = dp[i][j][k]
for j in range(n-1):
  for k in range((S+1)//2, S+1):
    cnt += dp[n][j][k] * (pow(2, n-j, mod) - 2)
    cnt %= mod
ans -= cnt*3
ans %= mod
print(ans)

Fixed submission:
n = int(input())
A = tuple(int(input()) for _ in range(n))
S = sum(A)
mod = 998244353
ans = pow(3, n, mod)
cnt = 0
dp = [[0]*(S+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for k in range(S+1):
    if k >= a:
      dp[i+1][k] = dp[i][k]*2 + dp[i][k-a]
    else:
      dp[i+1][k] = dp[i][k]*2
    dp[i+1][k] %= mod
for k in range((S+1)//2, S+1):
  ans -= dp[n][k]*3
  ans %= mod
if S%2 == 0:
  dp = [0]*(S//2+1)
  dp[0] = 1
  for i, a in enumerate(A):
    for k in range(S//2, -1, -1):
      if k >= a:
        dp[k] += dp[k-a]
  ans += dp[S//2]*3
  ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, abcde = int(input()), [ int(input()) for _ in range(5) ]
L = [0]*6
L[0] = n
ans = 0
while L[-1] < n:
  for i in range(4, -1, -1):
    L[i+1] += min(L[i], abcde[i])
    L[i] = max(L[i]-abcde[i], 0)
  ans += 1
print(ans)

Fixed submission:
n, a, b, c, d, e = [int(input()) for _ in range(6)]
m = min(a, b, c, d, e)
print(-(-n//m)+4)
Buggy python submission (verdict: Time Limit Exceeded):
M=10**9+7;B,W=map(int,input().split());F=[1];I=[1];p=q=0;C=lambda n,k:F[n]*pow(F[k]*F[n-k],M-2,M)if n>=k else 0
for i in range(1,B+W+1):F+=[F[-1]*i];I+=[I[-1]+I[-1]%2*M>>1];print((1-p+q)*I[1]%M);p+=C(i-1,B-1)*I[i];q+=C(i-1,W-1)*I[i]

Fixed submission:
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
B, W = map(int, input().split())
p = 0
q = 0
for i in range(1, B+W+1):
  ans = 1 - p + q
  ans %= MOD
  ans *= pow(2, MOD-2, MOD)
  ans %= MOD
  print(ans)
  p += comb(i-1, B-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  p %= MOD
  q += comb(i-1, W-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  q %= MOD
Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
MOD = 10**9+7

n, *C = map(int, read().split())
dp = [0]*(n+1)
dp[0] = 1
idx = [-1]*(10**5+1)
for i, c in enumerate(C, 1):
  dp[i] = dp[i-1]
  if idx[c] != -1 and idx[c] < i-1:
    dp[i] += dp[idx[c]]
    dp[i] %= MOD
  idx[c] = i
print(dp[-1])

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

n, *C = map(int, read().split())
dp = [0]*(n+1)
dp[0] = 1
idx = [-1]*(2*10**5+1)
for i, c in enumerate(C, 1):
  dp[i] = dp[i-1]
  if idx[c] != -1 and idx[c] < i-1:
    dp[i] += dp[idx[c]]
    dp[i] %= MOD
  idx[c] = i
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

def extract(a, i):
  return (a>>(i+1) << i) | (a&((1<<i)-1))

def space(a, i):
  return ((a>>i) << (i+1)) | (a&((1<<i)-1))

def compose(n, a, b):
  if n==1:
    return [a, b]
  for i in range(n):
    if (a>>i&1) ^ (b>>i&1):
      x = i
      a_bool = (a>>i & 1) << i
      b_bool = a_bool ^ (1 << i)
      a_dash = extract(a, i)
      b_dash = extract(b, i)
      c = a_dash ^ 1
      break
  Q = np.array(compose(n-1, a_dash, c), dtype=np.int64)
  R = np.array(compose(n-1, c, b_dash), dtype=np.int64)
  n_Q = space(Q, x) | a_bool
  n_R = space(R, x) | b_bool
  return n_Q.tolist() + n_R.tolist()
  
n, a, b = map(int, input().split())
cnt = 0
c = a^b
for i in range(n):
  cnt += c>>i & 1
if cnt&1:
  print("YES")
  print(*compose(n, a, b))
else:
  print("NO")

Fixed submission:
def extract(a, i):
  return (a>>(i+1) << i) | (a&((1<<i)-1))

def space(a, i):
  return ((a>>i) << (i+1)) | (a&((1<<i)-1))

def compose(n, a, b):
  if n==1:
    return [a, b]
  for i in range(n):
    if (a>>i&1) ^ (b>>i&1):
      x = i
      a_bool = (a>>i & 1) << i
      b_bool = a_bool ^ (1 << i)
      a_dash = extract(a, i)
      b_dash = extract(b, i)
      c = a_dash ^ 1
      break
  Q = compose(n-1, a_dash, c)
  R = compose(n-1, c, b_dash)
  n_Q = [space(i, x)|a_bool for i in Q]
  n_R = [space(i, x)|b_bool for i in R]
  return n_Q + n_R
  
n, a, b = map(int, input().split())
cnt = 0
c = a^b
for i in range(n):
  cnt += c>>i & 1
if cnt&1:
  print("YES")
  print(*compose(n, a, b))
else:
  print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

def xor(x):
  if x == 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))


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

def xor(x):
  if x <= 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

def xor(x):
  if x == 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))

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

def xor(x):
  if x <= 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))

Buggy python submission (verdict: Runtime Error):
def xor(x):
  if x==0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))

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

def xor(x):
  if x <= 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))
Buggy python submission (verdict: Runtime Error):
s = input()
c = 0
while "00" in s or "11" in s:
  c += 2 * s.count("00")
  c.replace("00", "")
  c += 2 * s.count("11")
  c.replace("11", "")
print(c)

Fixed submission:
s = input()
l = []
c = 0
for i in s:
  if not l:
    l.append(i)
  else:
    if i != l.pop():
      c += 2
    else:
      l.append(i)
      l.append(i)
print(c)
Buggy python submission (verdict: Runtime Error):
n = int(input())
c = 0
for i in range(n):
  x, u = map(int, input().split())
  if u == "BTC":
    x *= 380000
  c += x
print(c)

Fixed submission:
n = int(input())
c = 0
for i in range(n):
  x, u = map(lambda x:float(x) if x.replace(".", "").isdigit() else x, input().split())
  if u == "BTC":
    x *= 380000
  c += x
print(c)