Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

cnt = 0
n = 1

while N // 2*(5**n) > 0:
  a = N // 2*(5**n)
  cnt = cnt + a
  n = n + 1
  
print(cnt)

Fixed submission:
import math
N = int(input())

a1  = N // 10
a2  = N // 100
a3  = N // 1000
a4  = N // 10000
a5  = N // 100000
a6  = N // 1000000
a7  = N // 10000000
a8  = N // 100000000
a9  = N // 1000000000
a10 = N // 10000000000
a11 = N // 100000000000
a12 = N // 1000000000000
a13 = N // 10000000000000
a14 = N // 100000000000000
a15 = N // 1000000000000000
a16 = N // 10000000000000000
a17 = N // 100000000000000000
a18 = N // 1000000000000000000
a19 = N // 10000000000000000000

b1  = (N // 50) - a2
b2  = (N // 250  ) - a3
b3  = (N // 1250 ) - a4
b4  = (N // ((5**4)*10) ) - a5
b5  = math.ceil(N // ((5**5)*10 )) - a6
b6  = math.ceil(N // ((5**6)*10 )) - a7
b7  = math.ceil(N // ((5**7)*10 )) - a8
b8  = math.ceil(N // ((5**8)*10 )) - a9
b9  = math.ceil(N // ((5**9)*10 )) - a10
b10 = math.ceil(N // ((5**10)*10) ) - a11
b11 = math.ceil(N // ((5**11)*10) ) - a12
b12 = math.ceil(N // ((5**12)*10) ) - a13
b13 = math.ceil(N // ((5**13)*10) ) - a14
b14 = math.ceil(N // ((5**14)*10) ) - a15
b15 = math.ceil(N // ((5**15)*10) ) - a16
b16 = math.ceil(N // ((5**16)*10)) - a17
b17 = math.ceil(N // ((5**17)*10) ) - a18
b18 = math.ceil(N // ((5**18)*10) ) - a19
b19 = math.ceil(N // ((5**19)*10) )
b20 = math.ceil(N // ((5**20)*10) )
b21 = math.ceil(N // ((5**21)*10) )
b22 = math.ceil(N // ((5**22)*10) )
b23 = math.ceil(N // ((5**23)*10) )
b24 = math.ceil(N // ((5**24)*10) )
b25 = math.ceil(N // ((5**25)*10) )
b26 = math.ceil(N // ((5**26)*10) )


ans = a1*1 + a2*1+ a3*1+ a4*1 + a5*1+ a6*1+ a7*1+ a8*1+ a9*1+ a10*1+ a11*1+ a12*1+ a13*1+ a14*1+ a15*1+ a16*1+ a17*1+ a18*1+ a19*1
ans = ans + b1*1 + b2*1+ b3*1+ b4*1 + b5*1+ b6*1+ b7*1+ b8*1+ b9*1+ b10*1+ b11*1+ b12*1+ b13*1+ b14*1+ b15*1+ b16*1+ b17*1+ b18*1 + b19+b20+b21+b22+b23+b24+b25

if N % 2 == 1:
  print(0)
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

arr = list(str(S))
ans = []

for i in range(N):
  for j in range(N - i -1):
    for k in range(N - i - j - 2):
      
      a = int(arr[i])
      b = int(arr[j+i+1])
      c = int(arr[k+j+i+2])
      d = 100*a + 10*b + c
      
      if ans.count(d) == 0:
        ans.append(d)
      
      
a =len(ans)
print(a)

Fixed submission:
import math

N = int(input())
S = input()

arr = list(str(S))
cnt = 0

for i in range(1000):
  a = math.floor(i/100)
  b = math.floor((i-a*100)/10)
  c = i-a*100-b*10
  
  if str(a) in arr:
    an = arr.index(str(a))
    del arr[:an+1]
    
    if str(b) in arr:
      bn = arr.index(str(b))
      del arr[:bn+1]
      
      if str(c) in arr:
        cnt = cnt + 1
        
  arr = list(str(S))
      
print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

l = len(S)
if l % 2 == 1:
  print("No")
else:
  if S[0:N/2] == S[N/2+1:N]:
    print("Yes")
  else:
    print("No")

Fixed submission:
N = int(input())
S = input()

l = len(S)
if l % 2 == 1:
  print("No")
else:
  if S[0:int(N/2)] == S[int(N/2):int(N)]:
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())

List = list(map(int,input().split()))

List.sort()

a = []

for i in range(N):
  for j in range(i+1,N):
    a.append(List[i] + List[j])
    
a.sort()
ans = N * (N-1) * (N-2) / 6

for i in range(len(a)):
  b = a[i]
  c = bisect.bisect_left(List, b)
  ans -= (N-c)

print(int(ans))

Fixed submission:
import bisect
N = int(input())

List = list(map(int,input().split()))

List.sort()

a = []

for i in range(N):
  for j in range(i+1,N):
    a.append(List[i] + List[j])
    
a.sort()
ans = N * (N-1) * (N-2) / 6

for i in range(len(a)):
  b = a[i]
  c = bisect.bisect_left(List, b)
  ans -= (N-c)

print(int(ans))
Buggy python submission (verdict: Runtime Error):
import heapq

N,M = map(int, input().split())
List=list(map(-int,input().split()))

heapq.heapify(List)

for i in range(M):
  a = (-heapq.heappop(List)) // 2
  heapq.heappush(List, -a)
  
print(int(sum(List)))

Fixed submission:
import heapq

N,M = map(int, input().split())
List1=list(map(int,input().split()))
List=[]

for i in range(N):
  a = List1[i]
  List.append(-a)

heapq.heapify(List)

for i in range(M):
  a = (-heapq.heappop(List)) // 2
  heapq.heappush(List, -a)
  
print(int(-sum(List)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N,Q = map(int,input().split())
dist = {i:[] for i in range(1,N+1)}
oya = [-1 for i in range(N+1)]
oya[1] = 0

for i in range(N-1):
  a,b = map(int,input().split())
  dist[a].append(b)
  dist[b].append(a)

kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      oya[t] = a

ans = [0 for i in range(N+1)]
for q in range(Q):
  a,b = map(int,input().split())
  ans[a] += b
  
kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      p = oya[t]
      ans[t] += ans[p]
      
print(*ans[1:])

Fixed submission:
from collections import deque

N,Q = map(int,input().split())
dist = {i:[] for i in range(1,N+1)}
oya = [-1 for i in range(N+1)]
oya[1] = 0

for i in range(N-1):
  a,b = map(int,input().split())
  dist[a].append(b)
  dist[b].append(a)

kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      oya[t] = a

ans = [0 for i in range(N+1)]
for q in range(Q):
  a,b = map(int,input().split())
  ans[a] += b
  
kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      p = oya[t]
      ans[t] += ans[p]
      
print(*ans[1:])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

List=[''.join(sorted(input())) for i in range(N)]
List.sort()
List.extend("1")
cnt = 0

for i in range(N):
  a = List[i]
  b = List[i+1]
  if a != b:
    c = List.count(a)
    cnt = cnt + c * (c-1) / 2

print(int(cnt))

Fixed submission:
N = int(input())

List=[''.join(sorted(input())) for i in range(N)]
List.sort()
List.extend("1")
cnt = 0
num = 0

for i in range(N):
  a = List[i]
  b = List[i+1]
  if a != b:   
    cnt = cnt + num * (num+1) / 2
    num = 0 
  else:
    num = num + 1

print(int(cnt))
Buggy python submission (verdict: Runtime Error):
import heapq
N, M = map(int, input().split())
jobs = {m:[] for m in range(1,M+1) }

for i in range(N):
  hi,yen = map(int, input().split())
  jobs[hi].append(yen)
  
q = []
ans = 0
for i in range(1,M+1):
  for j in jobs[i]:
    heapq.heappush(q, -j)
  if len(q) > 0:
    a = heapq.heappop(q)
    ans += -a  
print(ans)

Fixed submission:
import heapq
N, M = map(int, input().split())
jobs = {m:[] for m in range(1,M+1) }

for i in range(N):
  hi,yen = map(int, input().split())
  if hi <= M:
    jobs[hi].append(yen)
  
q = []
ans = 0
for i in range(1,M+1):
  for j in jobs[i]:
    heapq.heappush(q, -j)
  if len(q) > 0:
    a = heapq.heappop(q)
    ans += -a  
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
cnt = 0

ai = A[0]
ai2 = A[1]

for i in range(N):

  bi = B[i]
  
  if ai <= bi:
    cnt += ai
    
    if ai2 <= (bi - ai):
      cnt += ai2
      ai = max(0, ai2-(bi - ai))
      ai2 = A[i+2]
    else:
      cnt += (bi - ai)
      ai = max(0, ai2-(bi - ai))
      ai2 = A[i+2]
      
  else:
    cnt += bi
    ai = A[i+1]
    ai2 = A[i+2]
  
print(int(cnt))

Fixed submission:
N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
cnt = 0

A.append(0)
A.append(0)

ai = A[0]
ai2 = A[1]

for i in range(N):

  bi = B[i]
  
  if ai <= bi:
    cnt += ai
    
    if ai2 <= (bi - ai):
      cnt += ai2
      ai = max(0, ai2-(bi - ai))
      ai2 = A[i+2]
    else:
      cnt += (bi - ai)
      ai = max(0, ai2-(bi - ai))
      ai2 = A[i+2]
      
  else:
    cnt += bi
    ai = A[i+1]
    ai2 = A[i+2]
  
print(int(cnt))
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N <= 10**9:
  List = [0,0,0,1,N,0]
else:
  a = -(-S//(10**9))
  b = a*10**9-S
  List = [0,0,10**9,b,a,1]
  
print(*List)

Fixed submission:
N = int(input())
a = -(-N//(10**9))
b = a*10**9-N
print(0, 0, 10**9, b, 1, a)
Buggy python submission (verdict: Runtime Error):
N = int(input())
List = list(map(int,input().split()))

List.sort()

a = List[N/2-1]
b = List[N/2]

print(int(b-a))

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

List.sort()

a = List[int(N/2-1)]
b = List[N//2]

print(int(b-a))
Buggy python submission (verdict: Time Limit Exceeded):
import re

H,W = map(int,input().split())
arr = []

for i in range(H):
  S = list(map(int,input().replace("#","0").replace(".","1")))
  arr.append(S)

L = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][j]
    elif arr[i][j-1] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    L[i].append(ans)

R = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][W-1-j]
    elif arr[i][W-j] == 0:
      ans = arr[i][W-1-j]
    else:
      ans = ans + 1
    R[i].insert(0, ans)

T = [[] for _ in range(H)]
for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[i][j]
    elif arr[i-1][j] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    T[i].append(ans)

U = [[] for _ in range(H)]
for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[H-1-i][j]
    elif arr[H-i][j] == 0:
      ans = arr[H-1-i][j]
    else:
      ans = ans + 1
    U[H-1-i].append(ans)

ans = []
for j in range(W):
  for i in range(H):
    if arr[i][j] != 0:
      a = L[i][j] + R[i][j] + T[i][j] + U[i][j] - 3
      ans.append(a)
      
print(int(max(ans)))

Fixed submission:
import re

H,W = map(int,input().split())
arr = []

for i in range(H):
  S = list(map(int,input().replace("#","0").replace(".","1")))
  arr.append(S)

ANS = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][j]
    elif arr[i][j-1] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    ANS[i].append(ans)

for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][W-1-j]
    elif arr[i][W-j] == 0:
      ans = arr[i][W-1-j]
    else:
      ans = ans + 1
    ANS[i][W-1-j] += ans

for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[i][j]
    elif arr[i-1][j] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    ANS[i][j] += ans

for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[H-1-i][j]
    elif arr[H-i][j] == 0:
      ans = arr[H-1-i][j]
    else:
      ans = ans + 1
    ANS[H-1-i][j] += ans

    
    
ans = []
for j in range(W):
  for i in range(H):
    if arr[i][j] != 0:
      a = ANS[i][j] - 3
      ans.append(a)
print(int(max(ans)))
Buggy python submission (verdict: Time Limit Exceeded):
A,P = map(int,input().split())


for i in range(10**111111):
  a =0

if ( A * 3 + P ) % 2 == 0:
  print(int( ( A * 3 + P ) / 2 ))
else:
  print( int(( A * 3 + P - 1) / 2 ))

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

if ( A * 3 + P ) % 2 == 0:
  print(int( ( A * 3 + P ) / 2 ))
else:
  print( int(( A * 3 + P - 1) / 2 ))
Buggy python submission (verdict: Runtime Error):
def resolve():
    N, K = [int(i) for i in input().split()]
    import math
    ans = 0
    for i in range(1, N + 1):
        if i < K:
            coin = math.ceil(math.log2(K / i))
            ans += (1 / N) * ((1 / 2)**coin)
        else:
            ans += (1 / N)
    print(ans)


resolve()


Fixed submission:
n,k=map(int,input().split())
ans=0
for i in range(1, n+1):
    tmp=1/n
    p=i
    while p<k:
        p=2*p
        tmp=tmp/2
    ans+=tmp
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

list = list(map(int,input().split()))
ans2 = 0

for i in range(N):
  l = list[0:i]
  
  if -(N-i)+1 == 0:
    r = []
  else:
    r = list[-(N-i)+1:]
    
  if l == []:
    ans = gcd_list(r)
  elif r == []:
    ans = gcd_list(l)
  else:
    a = gcd_list(r)
    b = gcd_list(l)
    ans = gcd(a, b)
    
  ans2 = max(ans2,ans)
  
print(ans2)

Fixed submission:
import math
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

List = list(map(int,input().split()))

a = List[0]
L = [0 for i in range(N)]
L[0] = a
for i in range(1,N):
  L[i] = gcd(List[i],L[i-1])
  
a = List[-1]
R = [0 for i in range(N)]
R[0] = a
for i in range(1,N):
  R[i] = gcd(List[-i-1],R[i-1])


p = 0
for i in range(N):
  if i == 0:
    ans = R[N-2]
  elif i == N-1:
    ans = L[-2]
  else:
    a = L[i-1]
    b = R[N-i-2]
    ans = gcd(a,b)
  p = max(p,ans)
  
print(int(p))
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

t1 = math.floor(N / A)
B = (t1 -1 ) * B
N = max(N % A,N-B)

t2 = math.floor(N / B)
C = (t2 -1 ) * C
N = max(N % B,N-C)

t3 = math.floor(N / C)
D = (t3 -1 ) * D
N = max(N % C,N-D)

t4 = math.floor(N / D)
E = (t4 -1 ) * E
N = max(N % D,N-E)

t5 = math.floor(N / E)

print(int(t1+t2+t3+t4+t5))

Fixed submission:
import math

N=int(input())
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())

print( math.ceil( N / min(A,B,C,D,E) ) +4 )
Buggy python submission (verdict: Runtime Error):
S = input()
List = list(S)

ans = 0
arr = []
for i in range(len(List)):
  if List[i] == "A" or List[i] == "C" or List[i] == "G" or List[i] == "T":
    ans += 1
  else:
    arr.append(ans)
    ans = 0
    
print(max(arr))


Fixed submission:
S = input()
List = list(S)

ans = 0
arr = []
for i in range(len(List)):
  if List[i] == "A" or List[i] == "C" or List[i] == "G" or List[i] == "T":
    ans += 1
  else:
    arr.append(ans)
    ans = 0
    
arr.append(ans)

print(max(arr))

Buggy python submission (verdict: Runtime Error):
S = input()
List = list(S)

ans = 0
arr = []
for i in range(len(List)):
  if List[i] == "A" or List[i] == "C" or List[i] == "G" or List[i] == "T":
    ans += 1
  else:
    arr.appned(ans)
    ans = 0
    
print(max(arr))

Fixed submission:
S = input()
List = list(S)

ans = 0
arr = []
for i in range(len(List)):
  if List[i] == "A" or List[i] == "C" or List[i] == "G" or List[i] == "T":
    ans += 1
  else:
    arr.append(ans)
    ans = 0
    
arr.append(ans)

print(max(arr))
Buggy python submission (verdict: Runtime Error):
N,Q = map(int,input().split())
S = list(input())

a = [0 for i in range(N)]
b = [0 for i in range(N)]

for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    a[i] = 1
    b[i+1] = 1
    
def cumsum(xs):
  result = [xs[0]]
  for x in xs[1:]:
    result.append(result[-1] + x)
  return result

A = cumsum(a)
B = cumsum(b)

for i in range(Q):
  l,r = map(int,input().split())
  print(B[r] - A[l])

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

a = [0 for i in range(N)]
b = [0 for i in range(N)]

for i in range(N-1):
  if S[i] == "A" and S[i+1] == "C":
    a[i] = 1
    b[i+1] = 1
    
def cumsum(xs):
  result = [xs[0]]
  for x in xs[1:]:
    result.append(result[-1] + x)
  result.append(0)
  result.sort()
  return result

A = cumsum(a)
B = cumsum(b)

for i in range(Q):
  l,r = map(int,input().split())
  print(int(B[r] - A[l-1]))
Buggy python submission (verdict: Runtime Error):
import math
N,M = map(int,input().split())

sq = math.sqrt(M)

for i in range(1,sq+1):
  if M % i == 0:
    if i <= math.floor(M/N):
      ans = i
    
print(int(ans))

Fixed submission:
import math
N,M = map(int,input().split())

sq = math.sqrt(M)
sq = math.floor(sq)


ans = 1
for i in range(1,sq+2):
  if M % i == 0:
    if i * N <= M:
      ans = max(i,ans)
    if M / i * N <= M:
      ans = max(M // i,ans)
if N == 1:
  print(int(M))
else:
  print(int(ans))

Buggy python submission (verdict: Runtime Error):
import math
N,M = map(int,input().split())

if M % N != 0:
  
  a = int(M % N)
  b = (M - a) / N
  c = math.gcd(a, b)
  print(c)
else:
  print(int(M/N))


Fixed submission:
import math
N,M = map(int,input().split())

sq = math.sqrt(M)
sq = math.floor(sq)


ans = 1
for i in range(1,sq+2):
  if M % i == 0:
    if i * N <= M:
      ans = max(i,ans)
    if M / i * N <= M:
      ans = max(M // i,ans)
if N == 1:
  print(int(M))
else:
  print(int(ans))

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

if M % N != 0:
  
  a = int(M % N)
  b = (M - a) / N
  c = math.gcd(a, b)
  print(c)
else:
  print(int(M/N))


Fixed submission:
import math
N,M = map(int,input().split())

sq = math.sqrt(M)
sq = math.floor(sq)


ans = 1
for i in range(1,sq+2):
  if M % i == 0:
    if i * N <= M:
      ans = max(i,ans)
    if M / i * N <= M:
      ans = max(M // i,ans)
if N == 1:
  print(int(M))
else:
  print(int(ans))
Buggy python submission (verdict: Runtime Error):
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
print(int(make_divisors(N)))

Fixed submission:
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return len(divisors)
  
ans = 0

for i in range(1,N+1):
  a = make_divisors(i)
  if a ==8 and i%2 == 1 :
    ans += 1
    
print(int(ans))
Buggy python submission (verdict: Runtime Error):
d, goal = map(int, input().split())
pc = [0] + [list(map(int, input().split())) for _ in range(d)]

def solve(goal, d):
  if d == 0:
    return 10**9
  n = min(goal//(100*d), pc[d][0])
  t = n * d * 100
  if n == pc[d][0]:
    t += pc[d][1]
  if t < goal:
    n += solve(goal-t, d-1)
  return min(n, solve(goal,d-1))

print(solve(g,d))


Fixed submission:
d, goal = map(int, input().split())
pc = [0] + [list(map(int, input().split())) for _ in range(d)]

def solve(goal, d):
  if d == 0:
    return 10**9
  n = min(goal//(100*d), pc[d][0])
  t = n * d * 100
  if n == pc[d][0]:
    t += pc[d][1]
  if t < goal:
    n += solve(goal-t, d-1)
  return min(n, solve(goal,d-1))

print(solve(goal,d))
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
l=len(s)

dp=[4*[0]for _ in range(l+1)]
dp[0][0]=1

for i in range(1,l+1):
  si = s[i-1]
  if si == "?":
    dp[i][0] = dp[i-1][0] * 3
    dp[i][1] = dp[i-1][1] * 3
    dp[i][2] = dp[i-1][2] * 3
    dp[i][3] = dp[i-1][3] * 3
  else:
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]
    dp[i][2] = dp[i-1][2]
    dp[i][3] = dp[i-1][3]
    
  if si == "A":
    dp[i][1] = dp[i-1][0] + dp[i][1]
  elif si == "B":
    dp[i][2] = dp[i-1][1] + dp[i][2]
  elif si == "C":
    dp[i][3] = dp[i-1][2] + dp[i][3]
  else:
    dp[i][1] = dp[i-1][0] + dp[i][1]
    dp[i][2] = dp[i-1][1] + dp[i][2]
    dp[i][3] = dp[i-1][2] + dp[i][3]
  
print(int(dp[-1][-1] % 1000000007))

Fixed submission:
s=input()
l=len(s)

dp=[4*[0]for _ in range(l+1)]
dp[0][0]=1

for i in range(1,l+1):
  si = s[i-1]
  if si == "?":
    dp[i][0] = dp[i-1][0] * 3
    dp[i][1] = dp[i-1][1] * 3
    dp[i][2] = dp[i-1][2] * 3
    dp[i][3] = dp[i-1][3] * 3
  else:
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]
    dp[i][2] = dp[i-1][2]
    dp[i][3] = dp[i-1][3]
    
  if si == "A":
    dp[i][1] = dp[i-1][0] + dp[i][1]
  elif si == "B":
    dp[i][2] = dp[i-1][1] + dp[i][2]
  elif si == "C":
    dp[i][3] = dp[i-1][2] + dp[i][3]
  else:
    dp[i][1] = dp[i-1][0] + dp[i][1]
    dp[i][2] = dp[i-1][1] + dp[i][2]
    dp[i][3] = dp[i-1][2] + dp[i][3]
  
  for j in range(4):
    dp[i][j] = dp[i][j] % 1000000007
  
print(int(dp[-1][-1]))
Buggy python submission (verdict: Time Limit Exceeded):
def ck(a,b,arr):
  if sum(arr[a:b]) == b - a:
    return 1
  else:
    return 0

N,M=map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]
List_2 = [0] * M
arr = [1] * N

for i in range(M):
  a = List[i][1]
  b = List[i][0]
  List_2[i] = [a,b]
  
List_2.sort()
  
for i in range(M):
  a = List_2[i][1]
  b = List_2[i][0]

  hantei = ck(a,b,arr)
  if hantei == 1:
    arr[b-1] = 0
  
print(int(N - sum(arr)))

Fixed submission:
def ck(a,b,arr):
  if arr >= a and arr < b:
    return 0
  else:
    return 1

N,M=map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]
List_2 = [0] * M
arr = 0
cnt = 0

for i in range(M):
  a = List[i][1]
  b = List[i][0]
  List_2[i] = [a,b]
  
List_2.sort()
  
for i in range(M):
  a = List_2[i][1]
  b = List_2[i][0]

  hantei = ck(a,b,arr)
  if hantei == 1:
    arr = b-1
    cnt += 1
  
print(int(cnt))
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().spkit())
arr = []

for i in range(N):
  a,b,c = map(int,input().spkit())
  arr.append(int(a+b+c))

arr.sort(reverse=True)

print(int(sum(arr[:M])))

Fixed submission:
N,M = map(int,input().split())
arr1 = []
arr2 = []
arr3 = []
arr4 = []
arr5 = []
arr6 = []
arr7 = []
arr8 = []

for i in range(N):
  a,b,c = map(int,input().split())
  arr1.append(int(a+b+c))
  arr2.append(int(a-b+c))
  arr3.append(int(a+b-c))
  arr4.append(int(a-b-c))
  arr5.append(int(-a+b+c))
  arr6.append(int(-a-b+c))
  arr7.append(int(-a+b-c))
  arr8.append(int(-a-b-c))

arr1.sort(reverse=True)
arr2.sort(reverse=True)
arr3.sort(reverse=True)
arr4.sort(reverse=True)
arr5.sort(reverse=True)
arr6.sort(reverse=True)
arr7.sort(reverse=True)
arr8.sort(reverse=True)

print(max(sum(arr1[:M]),sum(arr2[:M]),sum(arr3[:M]),sum(arr4[:M]),sum(arr5[:M]),sum(arr6[:M]),sum(arr7[:M]),sum(arr8[:M])))
Buggy python submission (verdict: Time Limit Exceeded):
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))



Fixed submission:
from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))

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

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  a = n
  cnt = 1
  b = fx(n-1)+1
  arr.append(b)
  while n-6**cnt >= 0:
    x = n-(6**cnt)
    b = fx(x)+1
    arr.append(b)
    cnt += 1
  cnt = 1
  while n-9**cnt >= 0:
    x = n-(9**cnt)
    b = fx(x)+1
    arr.append(b)
    cnt += 1
  return min(arr)
  
N = int(input())
print(fx(N))



Fixed submission:
from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))