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

for c in t:
    if c not in s:
        print(-1)
        exit()

i = 0
mod = len(s)
for c in t:
    while True:
        if s[i % mod] == c:
            i += 1
            break
        else:
            i += 1
    
print(i)


Fixed submission:
from bisect import bisect

def indexes(L, x):
    INDEXES = []
    for i in range(len(L)):
        if L[i] == x:
            INDEXES.append(i)
    return INDEXES


s = input()
t = input()

ss = s * 2
alphabets = "abcdefghijklmnopqrstuvwxyz"
INDEXES = {c:indexes(ss, c) for c in alphabets}

def index(i, c):
    return INDEXES[c][bisect(INDEXES[c], i)]

if not INDEXES[t[0]]:
    print(-1)
    exit()
now = INDEXES[t[0]][0]

answer = now + 1
mod = len(s)
for c in t[1:]:
    if not INDEXES[c]:
        print(-1)
        exit()
    next = index(now, c)
    answer += next - now
    now = next % mod

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

S = []
for _ in range(n):
    s = list(input())
    s.sort()
    S.append("".join(s))
S.sort()

C = []
i = 0
while i < n:
    c = S.count(S[i])
    if c > 1:
        C.append(c)
    i += c

ans = 0
for c in C:
    ans += c * (c - 1) // 2

print(ans)


Fixed submission:
n = int(input())

S = []
for _ in range(n):
    s = list(input())
    s.sort()
    S.append("".join(s))
S.sort()

C = []
c = 1
for i in range(n - 1):
    if S[i] == S[i + 1]:
        c += 1
    else:
        C.append(c)
        c = 1
C.append(c)

ans = 0
for c in C:
    ans += c * (c - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


n, m = map(int, input().split())

JOBS = []
for _ in range(n):
    a, b = map(int, input().split())
    JOBS.append((b, a))
JOBS.sort(reverse = True)

REWARDS = [0] * m
count = 0
for job in JOBS:
    i = m - job[1]
    while i >= 0:
        if REWARDS[i] == 0:
            REWARDS[i] = job[0]
            count += 1
            break
        else:
            i -= 1
    if count == m:
        break

answer = sum(REWARDS)
print(answer)


Fixed submission:
import sys
input = sys.stdin.readline
from heapq import*


n, m = map(int, input().split())

JOBS = {i:[] for i in range(1, m + 1)}
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        JOBS[a].append(b)

answer = 0
REWARDS = []
heapify(REWARDS)
for i in range(1, m + 1):
    for reward in JOBS[i]:
        heappush(REWARDS, -reward)
    if len(REWARDS) > 0:
        reward = -heappop(REWARDS)
        answer += reward

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, d = map(int, input().split())

x, y = max(c, d), min(c, d)
r = x - y
while r != 0:
    x, y = max(y, r), min(y, r)
    r = x - y
gcd = x
lcm = c * d // gcd

nc = b // c - (a - 1) // c
nd = b // d - (a - 1) // d
nlcm = b // lcm - (a - 1) // lcm

print((b - a + 1) - (nc + nd - nlcm))


Fixed submission:
a, b, c, d = map(int, input().split())

x, y = c, d
r = x % y
while r != 0:
    x, y = y, r
    r = x % y
gcd = y
lcm = c * d // gcd

nc = b // c - (a - 1) // c
nd = b // d - (a - 1) // d
nlcm = b // lcm - (a - 1) // lcm

print((b - a + 1) - (nc + nd - nlcm))
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

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


n, m = map(int, input().split())

A = [int(input()) for _ in range(m)]
for i in range(m - 1):
    if A[i + 1] - A[i] == 1:
        ans = 0
        print(ans)
        exit()

S = []
for a in A:
    S.extend((a - 1, a, a + 1))
S.insert(0, 0)
S.append(n)

ans = 1
for i in range(len(S) - 1):
    r = S[i + 1] - S[i]
    if r > 1:
        c = 0
        t_max = r // 2
        for t in range(t_max + 1):
            c += comb(r - t, t)
        ans *= c

ans %= 10**9 + 7
print(ans)


Fixed submission:
n, m = map(int, input().split())

S = [1] * (n + 1)
for _ in range(m):
    a = int(input())
    S[a] = 0

i = -3
for _ in range(n - 1):
    if S[i] != 0:
        S[i] = S[i + 1] + S[i + 2]
    i -= 1

ans = S[0] % (10**9 + 7)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())

l, r = map(int, input().split())
ID = list(range(l, r + 1))
for _ in range(m - 1):
    l, r = map(int, input().split())
    if r < min(ID):
        print(0)
        exit()
    elif max(ID) < l:
        print(0)
        exit()
    elif min(ID) >= l and max(ID) >= r:
        l = min(ID)
        ID.clear()
        ID.extend(range(l, r + 1))
    elif min(ID) < l and max(ID) >= r:
        ID.clear()
        ID.extend(range(l, r + 1))
    elif min(ID) < l and max(ID) < r:
        r = max(ID)
        ID.clear()
        ID.extend(range(l, r + 1))

print(len(ID))


Fixed submission:
n, m = map(int, input().split())

l, r = map(int, input().split())
for _ in range(m - 1):
    li, ri = map(int, input().split())
    if ri < l:
        print(0)
        exit()
    elif r < li:
        print(0)
        exit()
    elif l >= li and r >= ri:
        r = ri
    elif l < li and r >= ri:
        l, r = li, ri
    elif l < li and r < ri:
        l = li

print(r - l + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect


n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

for _ in range(m):
    b, c = map(int, input().split())
    i = bisect.bisect_left(A, c)
    if i >= b:
        A[:b] = [c] * b
    else:
        A[:i] = [c] * i
    A.sort()

answer = sum(A)
print(answer)


Fixed submission:
from heapq import *


n, m = map(int, input().split())
PAIRS = [[-a, -1] for a in map(int, input().split())]
heapify(PAIRS)

for _ in range(m):
    b, c = map(int, input().split())
    heappush(PAIRS, [-c, -b])

answer = 0
for _ in range(n):
    pair = heappop(PAIRS)
    answer += -pair[0]
    pair[1] += 1
    if pair[1] != 0:
        heappush(PAIRS, pair)

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *


n, m = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        a = heappop(A)
        if a < c:
            heappush(A, c)
        else:
            heappush(A, a)
            break

answer = sum(A)
print(answer)


Fixed submission:
from heapq import *


n, m = map(int, input().split())
PAIRS = [[-a, -1] for a in map(int, input().split())]
heapify(PAIRS)

for _ in range(m):
    b, c = map(int, input().split())
    heappush(PAIRS, [-c, -b])

answer = 0
for _ in range(n):
    pair = heappop(PAIRS)
    answer += -pair[0]
    pair[1] += 1
    if pair[1] != 0:
        heappush(PAIRS, pair)

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(m, n):
    r = m % n
    return n if r == 0 else gcd(n, r)


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

if n == 2:
    print(max(A))
    exit()

GCD = []
for i in range(n):
    A2 = A[:i] + A[i + 1:]
    g = gcd(A2[0], A2[1])
    for j in range(2, n - 1):
        g = gcd(g, A2[j])
        if g == 1:
            break
    GCD.append(g)

print(max(GCD))


Fixed submission:
def gcd(m, n):
    r = m % n
    return n if r == 0 else gcd(n, r)


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

GCD_left = A[:]
for i in range(1, n):
    GCD_left[i] = gcd(GCD_left[i - 1], GCD_left[i])
GCD_right = A[:]
for i in range(n - 2, -1, -1):
    GCD_right[i] = gcd(GCD_right[i], GCD_right[i + 1])

GCD = [1] * n
GCD[0], GCD[-1] = GCD_right[1], GCD_left[-2]
for i in range(1, n - 1):
    GCD[i] = gcd(GCD_left[i - 1], GCD_right[i + 1])

print(max(GCD))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s = "1" + input() + "1"

ZERO, ONE = [], []
now = "1"
count = 0
for c in s:
    if c == now:
        count += 1
    else:
        if now == "0":
            ZERO.append(count)
        else:
            ONE.append(count)
        now = c
        count = 1
ONE.append(count)
ONE[0] -= 1; ONE[-1] -= 1

m = len(ZERO)
if k >= m:
    print(n)
    exit()

answer = 0
for i in range(m - k + 1):
    temporary = sum(ZERO[i:i + k]) + sum(ONE[i:i + k + 1])
    answer = max(answer, temporary)

print(answer)


Fixed submission:
n, k = map(int, input().split())
s = "1" + input() + "1"

ZERO, ONE = [], []
now = "1"
count = 0
for c in s:
    if c == now:
        count += 1
    else:
        if now == "0":
            ZERO.append(count)
        else:
            ONE.append(count)
        now = c
        count = 1
ONE.append(count)
ONE[0] -= 1; ONE[-1] -= 1

m = len(ZERO)
if k >= m:
    print(n)
    exit()

answer = temporary = sum(ZERO[:k]) + sum(ONE[:k + 1])
for i in range(m - k):
    temporary += ZERO[i + k] + ONE[i + k + 1]
    temporary -= ZERO[i] + ONE[i]
    answer = max(answer, temporary)

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


n, m = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(m):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

DISTANCE = {i:-1 for i in range(1, n + 1)}
DISTANCE[1] = 0
QUEUE = [1]
while QUEUE:
    now = QUEUE.pop(0)
    for v in GRAPH[now]:
        if DISTANCE[v] != -1:
            continue
        DISTANCE[v] = DISTANCE[now] + 1
        QUEUE.append(v)

print("POSSIBLE" if DISTANCE[n] == 2 else "IMPOSSIBLE")


Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque


n, m = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(m):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

DISTANCE = {i:-1 for i in range(1, n + 1)}
DISTANCE[1] = 0
QUEUE = deque([1])
while QUEUE:
    now = QUEUE.popleft()
    for v in GRAPH[now]:
        if DISTANCE[v] != -1:
            continue
        DISTANCE[v] = DISTANCE[now] + 1
        QUEUE.append(v)

print("POSSIBLE" if DISTANCE[n] == 2 else "IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
import sys

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

for x in range(n-1)
  	if nums[x] > nums[x+1]:
    	nums[x] -= 1

    if nums[x] > nums[x+1]:
      	print('No')
      	sys.exit()

print('Yes')

Fixed submission:
import sys
 
n = int(input())
nums = list(map(int, input().split()))
maxnum = 0

for x in range(n):
    if maxnum < nums[x]:
        maxnum = nums[x]
    if maxnum - nums[x] > 1:
        print('No')
        sys.exit() 
 
print('Yes')
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
 
n,*a = map(int, open(0).read().split())
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))

Fixed submission:
a,b,t = map(int,input().split())
print(0 if a>t else (t//a)*b)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

n=int(input());Alist=list(map(int,input().split()))

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

M_list = []
for i in range(n):
    alist = Alist[:i] + Alist[i+1:]
    M_list.append(gcd_L(alist))

print(max(M_list))

Fixed submission:
a,b,t = map(int,input().split())
print(0 if a>t else (t//a)*b)

Buggy python submission (verdict: Runtime Error):
from math import gcd
from functools import reduce

n=int(input());Alist=list(map(int,input().split()))

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

M_list = []
for i in range(n):
    alist = Alist[:i] + Alist[i+1:]
    M_list.append(gcd_L(alist))

print(max(M_list))

Fixed submission:
a,b,t = map(int,input().split())
print(0 if a>t else (t//a)*b)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

n=int(input());Alist=list(map(int,input().split()))

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

M_list = []
for i in range(n):
    alist = Alist[:i] + Alist[i+1:]
    M_list.append(gcd_L(alist))

print(max(M_list))

Fixed submission:
from fractions import gcd
 
n,*a = map(int, open(0).read().split())
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))
Buggy python submission (verdict: Time Limit Exceeded):
l, r = map(int, input().split())
mod = 2019
ans = l*r%mod
for i in range(l, r):
    for j in range(i+1, r+1):
        tmp = i*j%mod
        if ans > tmp:
            ans = tmp
print(ans)

Fixed submission:
L,R=map(int,input().split())
c=2019
z=0
for i in range(L,R+1):
    for j in range(i+1,R+1):
        a=i*j
        b=a%2019
        if c>b:
            c=b
        if c==0:
            z=1
            break
    if z==1:
        break
print(c)
Buggy python submission (verdict: Runtime Error):
n,k = map(int, input().split())
from math import factorial
import numpy as np
for i in range(1,k+1):
    perm = factorial(n-k+1)/factorial((n-k+1)-i)
    tmp = np.ceil(k/i)
    a, b = int(k//tmp), int(k%tmp)
    perm /= (factorial(a)*factorial(b))
    print(int(perm)%(10**9+7))

Fixed submission:
import math
N,K = (int(x) for x in input().split())
R = N - K
mod = 10**9 + 7
def fact(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(1,K+1):
    ans = 0 if N - K + 1 < i else fact(R+1, i)*fact(K-1,i-1)
    print(int(ans)%mod)
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))


Fixed submission:
pre = 0
for i in list(input()):
    if i == pre:
        print("Bad")
        exit()
    pre = i
print("Good")

Buggy python submission (verdict: Runtime Error):
pre = None
for i in list(input()):
	if i == pre:
      	print("Bad")
        exit()
    pre = i
print("Good")

Fixed submission:
pre = 0
for i in list(input()):
    if i == pre:
        print("Bad")
        exit()
    pre = i
print("Good")
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)/gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm))

Fixed submission:
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int, input().split())
sub=b-a
tmpc=sub//c
tmpd=sub//d
import fractions
def lcm(x,y):
    return (x*y) // fractions.gcd(x,y)
tmplcm=sub//lcm(c,d)
print(max(sub-(tmpc+tmpd-tmplcm)), 0)

Fixed submission:
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int, input().split())
sub=b-a
tmpc=sub//c
tmpd=sub//d

import math
def lcm(x,y):
  return (x*y) // math.gcd(x,y)

tmplcm=sub//lcm(c,d)
print(sub-(tmpc+tmpd-tmplcm))

Fixed submission:
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int, input().split())
# for i , a<i<b, i % c|d != 0
sub=b-a
tmpc=sub//c
tmpd=sub//d
import math
def lcm(a,b):
    return (a*b) // math.gcd(a,b)
tmplcm=sub//lcm(c,d)
print(sub-(tmpc+tmpd-tmplcm))

Fixed submission:
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0 
# left
for i in range(min(n, k) + 1):
    # right
    for j in range(min(n, k) - i + 1):
        par_seq = sorted(v[:i] + v[-j:] if j != 0 else v[:i])
        par_seq_sum = sum(par_seq)
        if par_seq_sum > ans:
            ans = par_seq_sum
        m = k - (i + j)
        tmp = max([sum(par_seq[i:]) for i in range(min(m, len(par_seq)))])
        if tmp > ans:
          ans = tmp
print(ans)

Fixed submission:
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0 
# left
for i in range(min(n, k) + 1):
    # right
    for j in range(min(n, k) - i + 1):
        # print(i,j)
        par_seq = sorted(v[:i] + v[-j:] if j != 0 else v[:i])
        par_seq_sum = sum(par_seq)
        if par_seq_sum > ans:
            ans = par_seq_sum
        ope = k - (i + j)
        # print(par_seq, par_seq_sum)
        for _ in range(min(ope, len(par_seq))):
            rm = par_seq.pop(0)
            if rm < 0 and sum(par_seq) > ans:
                ans = sum(par_seq)

print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
mis,mas=[],[]
for _ in range(m-1):
  tmp=list(map(int,input().split()))
  mis.append(tmp[0])
  mas.append(tmp[1])
ans=max(mas)-min(mis)
print(ans if ans>0 else 0)

Fixed submission:
n,m=map(int,input().split())
mis,mas=[],[]
for _ in range(m):
  tmp=list(map(int,input().split()))
  mis.append(tmp[0])
  mas.append(tmp[1])
ans=min(mas)-max(mis)+1
print(ans if ans>0 else 0)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

from functools import reduce
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def gcds(*numbers):
    return reduce(gcd, numbers)

ans = 0
for i in range(len(a)):
    aa = a.copy()
    aa.pop(i)
    g = gcds(*aa)
    ans = g if g > ans else ans
print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

from functools import reduce
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
"""
def gcds(*numbers):
    return reduce(gcd, numbers)
"""
l = [0 for _ in range(n)]

for i in range(1, n):
    l[i] = gcd(l[i - 1], a[i - 1])
last_gcd = 0
for i in range(n - 2, -1, -1):
    last_gcd = gcd(last_gcd, a[i + 1])
    l[i] = gcd(last_gcd, l[i])
print(max(l))
Buggy python submission (verdict: Runtime Error):
i, j = map(int, input().split())
print(max(i + j, i * 2 - 1, j * 2 - 1)

Fixed submission:
i, j = map(int, input().split())
print(max(i + j, i * 2 - 1, j * 2 - 1))
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    tar = S[l-1:r]
    print(tar.count('AC'))

Fixed submission:
N, Q = map(int, input().split())
S = input()
imosu = [0] * (N + 1)
for i in range(N):
    imosu[i + 1] = imosu[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(imosu[r-1]-imosu[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    tar = S[l-1:r]
    tar = tar.replace('AC', '@')
    print(tar.count('@'))

Fixed submission:
N, Q = map(int, input().split())
S = input()
imosu = [0] * (N + 1)
for i in range(N):
    imosu[i + 1] = imosu[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(imosu[r-1]-imosu[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = list(input())
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    tar = S[l-1:r]
    length = r - l + 1
    for i in range(length - 1):
        if tar[i] == 'A':
            if tar[i + 1] == 'C':
                ans += 1
    print(ans)

Fixed submission:
N, Q = map(int, input().split())
S = input()
imosu = [0] * (N + 1)
for i in range(N):
    imosu[i + 1] = imosu[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(imosu[r-1]-imosu[l-1])
Buggy python submission (verdict: Runtime Error):
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1] # 順序の入れ替え
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if check(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    print(memo)
    return ret

print(dfs(0, 'TTT'))


Fixed submission:
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1] # 順序の入れ替え
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if check(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
shop = []
for _ in range(N):
    a, b = map(int, input().split())
    shop.append([a,b])
shop.sort()

cur = 0
cur_v = 0
for a, b in shop:
    for i in range(b):
        cur += 1
        cur_v += a
        if cur == M:
            print(cur_v)
            break

Fixed submission:
N, M = map(int, input().split())
shop = []
for _ in range(N):
    a, b = map(int, input().split())
    shop.append([a,b])
shop.sort()

cur = 0
cur_v = 0
for a, b in shop:
    if cur + b > M:
        cur_v += (M - cur) * a
        break
    else:
        cur += b
        cur_v += a * b
print(cur_v)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
l = list(range(A,B))
l += [B]
l = [list("{:0>40}".format(format(i, 'b'))) for i in l]

import numpy as np
l = np.array(l)

ans = ''
for i in range(40):
    if np.sum(l[:, i] == '1') % 2 == 1:
        ans += '1'
    else:
        ans += '0'
print(int(ans, 2))

Fixed submission:
# A, B = map(int, input().split())
# l = list(range(A,B))
# l += [B]
# l = [list("{:0>42}".format(format(i, 'b'))) for i in l]

# import numpy as np
# l = np.array(l)

# ans = ''
# for i in range(42):
#     if np.sum(l[:, i] == '1') % 2 == 1:
#         ans += '1'
#     else:
#         ans += '0'
# print(int(str(ans), 2))

A, B = map(int, input().split())
def xor(x):
    mod = x % 4
    if mod == 0:
        return x
    elif mod == 1:
        return 1
    elif mod == 2:
        return x ^ 1
    elif mod == 3:
        return 0
print(xor(A-1) ^ xor(B))
Buggy python submission (verdict: Runtime Error):
S = list(input())

def f(S):
    new_array = []
    mark = False
    if len(S) == 2:
        if S[0] != S[1]:
            return []
        else:
            return S

    for i in range(0, len(S) - 2):
        if i % 3 == 0:
            if S[i] == S[i + 1] and S[i + 1] == S[i + 2]:
                new_array += [S[i], S[i+1], S[i+2]]
            elif S[i] != S[i + 1]:
                new_array += [S[i+2]]
                if mark == False:
                    mark = True
            elif S[i + 1] != S[i + 2]:
                new_array += [S[i]]
                if mark == False:
                    mark = True
    
    if len(S) % 3 == 1:
        if S[-2] != S[-1]:
            new_array.pop(-1)
        else:
            new_array += [S[-1]]
    elif len(S) % 3 == 2:
        if S[-2] == S[-1]:
            new_array += [S[-2], S[-1]]

    if mark == True:
        return f(new_array)
    else:
        return new_array


print(len(S) - len(f(S)))

Fixed submission:
S = list(input())
print(min(S.count('0'), S.count('1')) * 2)