Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
S = input()
l = len(S)
dp = [0,0,1]
ans = 0
for i in range(l):
    if S[i] == 'A':
        dp[0] += dp[2]
        dp[0] %= mod
    if S[i] == 'B':
        dp[1] += dp[0]
        dp[1] %= mod
    if S[i] == 'C':
        ans += dp[1]
        ans %= mod
    if S[i] == '?':
        dp1 = dp[:]
        dp2 = dp[:]
        dp3 = dp[:]
        dp1[0] += dp1[2]
        dp2[1] += dp2[0]
        ans *= 3
        ans += dp3[1]
        ans %= mod
        dp[0] = (dp1[0]+dp2[0]+dp3[0]) % mod
        dp[1] = (dp1[1]+dp2[1]+dp3[1]) % mod
        dp[2]*= 3
print(ans)

Fixed submission:
mod = 10**9+7
S = input()
l = len(S)
dp = [0,0,1]
ans = 0
for i in range(l):
    if S[i] == 'A':
        dp[0] += dp[2]
        dp[0] %= mod
    if S[i] == 'B':
        dp[1] += dp[0]
        dp[1] %= mod
    if S[i] == 'C':
        ans += dp[1]
        ans %= mod
    if S[i] == '?':
        dp1 = dp[:]
        dp2 = dp[:]
        dp3 = dp[:]
        dp1[0] += dp1[2]
        dp2[1] += dp2[0]
        ans *= 3
        ans += dp3[1]
        ans %= mod
        dp[0] = (dp1[0]+dp2[0]+dp3[0]) % mod
        dp[1] = (dp1[1]+dp2[1]+dp3[1]) % mod
        dp[2]*= 3
        dp[2] %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
mod = 998244353
N,A,B,K = map(int,input().split())
def cmb(n,k):
    return fac[n]*inv_fac[n-k]*inv_fac[k] % mod
fac = [1]
for i in range(1,N+1):
    fac.append(fac[-1]*i % mod)
inv_fac = [pow(fac[N],mod-2,mod)]
for i in range(1,N+1)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]

ans = 0
for i in range(N+1):
    if i*A > K:
        break
    if (K-i*A) % B == 0:
        j = (K-i*A)//B
        ans += cmb(N,i)*cmb(N,j)
        ans %= mod
print(ans)

Fixed submission:
mod = 998244353
N,A,B,K = map(int,input().split())
def cmb(n,k):
    return fac[n]*inv_fac[n-k]*inv_fac[k] % mod
fac = [1]
for i in range(1,N+1):
    fac.append(fac[-1]*i % mod)
inv_fac = [pow(fac[N],mod-2,mod)]
for i in range(1,N+1)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]

ans = 0
for i in range(N+1):
    if i*A > K:
        break
    if (K-i*A) % B == 0:
        j = (K-i*A)//B
        if j <= N:
            ans += cmb(N,i)*cmb(N,j)
            ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = []
like = []
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.append(p)
    integer = [i for i in integer if i % p != 0]
prime = prime + integer
for i in range(len(prime)):
    if ((prime[i]+1)//2) in prime:
        like.append(prime[i])
q = int(input())
for i in range(q):
    count = 0
    l,r = map(int,input().split())
    for j in range(l,r+1):
        if j in like:
            count += 1
    print(count)

Fixed submission:
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = []
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.append(p)
    integer = [i for i in integer if i % p != 0]
prime = prime + integer
like = []
likesum = [0]*(n+1)
for i in range(len(prime)):
    if (prime[i]+1)//2 in prime:
        like.append(prime[i])
for i in range(n):
    if i in like:
        likesum[i+1] = likesum[i] + 1
    else:
        likesum[i+1] = likesum[i]    
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(likesum[r+1]-likesum[l])
Buggy python submission (verdict: Runtime Error):
n = int(input())
k = int(input())
x = map(int,input().split())
ans = 0
for i in range(n):
    ans += min(abs(x[i]-k),x[i])
print(ans*2)


Fixed submission:
n = int(input())
k = int(input())
x = list(map(int,input().split()))
ans = 0
for i in range(n):
    ans += min(abs(x[i]-k),x[i])
print(ans*2)
Buggy python submission (verdict: Runtime Error):
Q,H,S,D = map(int,input().split())
X = min(4*Q,2*H,S)
Y = min(2*X,D)
print((N//2)*Y+(N%2)*X)

Fixed submission:
Q,H,S,D = map(int,input().split())
N = int(input())
X = min(4*Q,2*H,S)
Y = min(2*X,D)
print((N//2)*Y+(N%2)*X)
Buggy python submission (verdict: Runtime Error):
n = int(input())
for i in range(8):
    if int(2**(7-i)) <= n:
        print(2**(7-i)
        exit()

Fixed submission:
n = int(input())
for i in range(8):
    if int(2**(7-i)) <= n:
        print(int(2**(7-i)))
        exit()
Buggy python submission (verdict: Runtime Error):
from time import time
t = time()
count = 0
a = int(input())
b = int(input())
c = int(input())
while True:
    if a % 2 != 0 or b % 2 != 0 or c % 2 != 0:
        print(count)
        exit()
    count += 1
    a1 = b//2+c//2
    b1 = c//2+a//2
    c1 = a//2+b//2
    a = a1
    b = b1
    c = c1
    if time()-t >= 1.8:
        print(-1)
        exit()

Fixed submission:
from time import time
t = time()
count = 0
a,b,c = map(int,input().split())
while True:
    if a % 2 != 0 or b % 2 != 0 or c % 2 != 0:
        print(count)
        exit()
    count += 1
    a1 = b//2+c//2
    b1 = c//2+a//2
    c1 = a//2+b//2
    a = a1
    b = b1
    c = c1
    if time()-t >= 1.8:
        print(-1)
        exit()
Buggy python submission (verdict: Runtime Error):
x,y = map(int,input().split())
ans = 10000000000
for a,b,c in [(x,y,0)(x,-y,1)(-x,y,1)(-x,-y,2)]:
    if a < b:
        ans = min(ans,b-a+c)
print(ans)

Fixed submission:
x,y = map(int,input().split())
ans = 10000000000
for a,b,c in [(x,y,0),(x,-y,1),(-x,y,1),(-x,-y,2)]:
    if a <= b:
        ans = min(ans,b-a+c)
print(ans)
Buggy python submission (verdict: Runtime Error):
N,X,M=map(int,input().split())
F=(N-1).bit_length()

A=[[0]*M for _ in range(F)]

for x in range(M):
    A[0][x]=(x*x)%M

for d in range(1,F):
    for x in range(M):
        A[d][x]=A[d-1][A[d-1][x]]

S=[[0]*M for _ in range(F)]
for x in range(M):
    S[0][x]=A[0][x]

for d in range(1,F):
    for x in range(M):
        S[d][x]=S[d-1][x]+S[d-1][A[d-1][x]]

Ans=0
depth=0
N-=1
Y=X
while N>0:
    if N%2:
        Ans+=S[depth][X]
        X=A[depth][X]
    depth+=1
    N>>=1
print(Ans+Y)

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

if N==1 or M==1:
    print(X)
    exit()

F=(N-1).bit_length()

A=[[0]*M for _ in range(F)]

for x in range(M):
    A[0][x]=(x*x)%M

for d in range(1,F):
    for x in range(M):
        A[d][x]=A[d-1][A[d-1][x]]

S=[[0]*M for _ in range(F)]
for x in range(M):
    S[0][x]=A[0][x]

for d in range(1,F):
    for x in range(M):
        S[d][x]=S[d-1][x]+S[d-1][A[d-1][x]]

Ans=0
depth=0
N-=1
Y=X
while N>0:
    if N%2:
        Ans+=S[depth][X]
        X=A[depth][X]
    depth+=1
    N>>=1
print(Ans+Y)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def dist(A,B):
    return abs(A[0]-B[0])+abs(A[1]-B[1])

N=int(input())
P=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    P[i]=(x,y)

P=list(set(P))
N=len(P)
X=set(range(N))

S=[0]*N
D=[]
for k in range(N):
    if S[k]==0:
        S[k]=1
        Old_Old_=0
        Old_I=-1
        I=k
        Flag=False
        Y=set()
        while True:
            M=-1
            Old_Old_I=Old_I
            Old_I=I
            for i in X:
                if M<dist(P[I],P[i]):
                    J=i
                    M=dist(P[I],P[i])

            if J==Old_Old_I and Flag:
                break
            I=J
            S[I]=1
            Flag=True

        X-=Y
        D.append(dist(P[Old_I],P[J]))

print(max(D))

Fixed submission:
N=int(input())
Z=[0]*N
W=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    Z[i]=x+y
    W[i]=x-y

alpha=max(Z)-min(Z)
beta=max(W)-min(W)
print(max(alpha,beta))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def dist(A,B):
    return abs(A[0]-B[0])+abs(A[1]-B[1])

N=int(input())
P=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    P[i]=(x,y)

P=list(set(P))
N=len(P)

S=[0]*N
D=[]
for k in range(N):
    if S[k]==0:
        S[k]=1
        Old_Old_=0
        Old_I=-1
        I=k
        Flag=False
        while True:
            M=-1
            Old_Old_I=Old_I
            Old_I=I
            for i in range(N):
                if M<dist(P[I],P[i]):
                    J=i
                    M=dist(P[I],P[i])

            if J==Old_Old_I and Flag:
                break
            I=J
            S[I]=1
            Flag=True

    D.append(dist(P[Old_I],P[J]))

print(max(D))

Fixed submission:
N=int(input())
Z=[0]*N
W=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    Z[i]=x+y
    W[i]=x-y

alpha=max(Z)-min(Z)
beta=max(W)-min(W)
print(max(alpha,beta))
Buggy python submission (verdict: Runtime Error):
def f(S):
    if S=="":
        return 0
    else:
        return f(S[:-1])+int(S[-1])

N=input()
if f(N)%9:
    print("No")
else:
    print("Yes")


Fixed submission:
N=input()

S=0
for a in N:
    S+=int(a)

if S%9:
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
R,C,K=map(int,input().split())

Value=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    Value[r][c]=v

DP=[[[0,0,0,0] for _ in range(C+1) ] for __ in range(R+1)]

for y in range(1,R+1):
    for x in range(1,C+1):
        #右に移動
        for k in range(0,3+1):
            DP[y][x][k]=DP[y][x-1][k]

        for k in range(1,3+1):
            DP[y][x][k]=max(DP[y][x][k],DP[y][x-1][k-1]+Value[y][x])

        #下に移動
        G=max(DP[y-1][x])
        DP[y][x][0]=max(DP[y][x][0],G)

        DP[y][x][1]=max(DP[y][x][1],DP[y][x][0]+Value[y][x])


print(max(DP[-1][-1]))

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

Value=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    Value[r][c]=v

DP=[[0,0,0,0] for _ in range(C+1) ]

for y in range(1,R+1):
    #下に移動
    for x in range(1,C+1):
        DP[x][0]=max(DP[x])
        DP[x][1]=DP[x][0]+Value[y][x]
        DP[x][2]=DP[x][3]=0

    #右に移動
    for x in range(1,C+1):
        for k in range(0,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k])

        for k in range(1,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k-1]+Value[y][x])

print(max(DP[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
R,C,K=map(int,input().split())
Item=[["*"]*(C+1)]+[["*"]+[0]*C for _ in range(R)]
T=3

for _ in range(K):
    y,x,v=map(int,input().split())
    Item[y][x]=v

DP=[[[0]*(T+1) for _ in range(C+1)] for _ in range(R+1)]

for y in range(1,R+1):
    for x in range(1,C+1):
        #右に移動
        for k in range(1,T+1):
            DP[y][x][k]=max(DP[y][x][k],DP[y][x-1][k],DP[y][x-1][k-1]+Item[y][x])

        #下に移動
        if y<R:
            for k in range(T+1):
                DP[y+1][x][0]=DP[y][x][-1]
                DP[y+1][x][1]=DP[y+1][x][2]=DP[y+1][x][3]=DP[y+1][x][0]+Item[y+1][x]

print(max(DP[-1][-1]))

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

Value=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    Value[r][c]=v

DP=[[0,0,0,0] for _ in range(C+1) ]

for y in range(1,R+1):
    #下に移動
    for x in range(1,C+1):
        DP[x][0]=max(DP[x])
        DP[x][1]=DP[x][0]+Value[y][x]
        DP[x][2]=DP[x][3]=0

    #右に移動
    for x in range(1,C+1):
        for k in range(0,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k])

        for k in range(1,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k-1]+Value[y][x])

print(max(DP[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))

M=[N]*N

for i in range(K):
    L=[0]*(N+1)
    for j in range(N):
        L[max(0,j-A[j])]+=1
        L[min(N,j+A[j]+1)]-=1
        
    S=0
    for j in range(N):
        S+=L[j]
        A[j]=S

    #if A==M:
    #    break

for i in range(N):
    print(A[i],end=" ")
print()


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

M=[N]*N

for i in range(K):
    L=[0]*(N+1)
    for j in range(N):
        L[max(0,j-A[j])]+=1
        L[min(N,j+A[j]+1)]-=1
        
    S=0
    for j in range(N):
        S+=L[j]
        A[j]=S

    if A==M:
        break

for i in range(N):
    print(A[i],end=" ")
print()
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
P=list(map(int,input().split()))

A={}

for i in range(N):
    A[i+1]=P[i]

f=True
U=[]

v=1

k=0

while (v not in set(U)) and (k<=K):
    U.append(v)
    v=A[v]
    k+=1
    
if v not in U:
    print(U[-1])
else:
    g=U.index(v)
    U=U[g:]
    K-=g

    m=len(U)
    print(U[K%m])


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

A={k+1:P[k] for k in range(N)}


U=list()
S=set()
x=1
k=0

while (x not in S) and (k<=K):
    U.append(x)
    S.add(x)
    
    x=A[x]
    k+=1

if k>K:
    print(U[-1])
else:
    d=U.index(x)
    V=U[d:]
    print(V[(K-d)%len(V)])

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

A={}

for i in range(N):
    A[i+1]=P[i]

f=True
U=[]
v=1

k=0

while (v not in U) and (k<=K):
    U.append(v)
    v=A[v]
    k+=1
    
if v not in U:
    print(U[-1])
else:
    g=U.index(v)
    U=U[g:]
    K-=g

    m=len(U)
    print(U[K%m])


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

A={k+1:P[k] for k in range(N)}


U=list()
S=set()
x=1
k=0

while (x not in S) and (k<=K):
    U.append(x)
    S.add(x)
    
    x=A[x]
    k+=1

if k>K:
    print(U[-1])
else:
    d=U.index(x)
    V=U[d:]
    print(V[(K-d)%len(V)])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

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

S=0
for i in range(N):
    for j in range(i,N):
        if abs(i-j)==A[i]+A[j]:
            S+=1

print(S)

Fixed submission:
def Binary_Search_Small_Count(A,x,equal=False,sort=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()

    if A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Equal_Count(A,x,sort=False):
    """2分探索によって,xの個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if x<A[0] or A[-1]<x:
        return 0

    X=Binary_Search_Small_Count(A,x,equal=True)
    Y=Binary_Search_Small_Count(A,x,equal=False)
    return X-Y
#================================================
N=int(input())
A=["*"]+list(map(int,input().split()))

B=[0]*N
for j in range(1,N+1):
    B[j-1]=j-A[j]
B.sort()

K=0
del A[0]
for i in range(1,N+1):
    K+=Binary_Search_Equal_Count(B,i+A[i-1],False)
print(K)

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

H=[0]+list(map(int,input().split()))

J={x:[] for x in range(1,N+1)}

for i in range(M):
    a,b=map(int,input().split())
    J[a].append(b)
    J[b].append(a)

S=0
for x in J:
    f=1
    for y in J[x]:
        if H[x]<=H[y]:
            f=0
    S+=f

print(S)


Fixed submission:
def Binary_Search_Small_Count(A,x,equal=False,sort=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()

    if A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Equal_Count(A,x,sort=False):
    """2分探索によって,xの個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if x<A[0] or A[-1]<x:
        return 0

    X=Binary_Search_Small_Count(A,x,equal=True)
    Y=Binary_Search_Small_Count(A,x,equal=False)
    return X-Y
#================================================
N=int(input())
A=["*"]+list(map(int,input().split()))

B=[0]*N
for j in range(1,N+1):
    B[j-1]=j-A[j]
B.sort()

K=0
del A[0]
for i in range(1,N+1):
    K+=Binary_Search_Equal_Count(B,i+A[i-1],False)
print(K)
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
L=len(S)
M=2019

k=0
for i in range(L):
    for j in range(i,L):
        if int(S[i:j+1])%M==0:
            k+=1

print(k)


Fixed submission:
S=list(map(int,input()))
L=len(S)
M=2019
d=10

U=[]
for x in range(L):
    if x==0:
        U=[1]
    else:
        U.append((U[-1]*d)%M)
        
T=[0]
for x in range(1,L+1):
    T.append((T[-1]+S[-x]*U[x-1])%M)

D={}
for x in T:
    if x in D:
        D[x]+=1
    else:
        D[x]=1

r=0
for x in D.values():
    r+=(x*(x-1))//2

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
def Dict_Choice(D):
    S=0
    for k in D:
        x=D[k]
        S+=(x*(x-1))//2
    return S

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

D={}
for i in range(N):
    if A[i] in D:
        D[A[i]]+=1
    else:
        D[A[i]]=1

for i in range(N):
    y=A[i]
    D[y]-=1
    print(Dict_Choice(D))
    D[y]+=1


Fixed submission:
def Dict_Choice(D):
    S=0
    for k in D:
        x=D[k]
        S+=(x*(x-1))//2
    return S

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

D={}
for i in range(N):
    if A[i] in D:
        D[A[i]]+=1
    else:
        D[A[i]]=1

E={}
for k in D:
    x=D[k]
    E[k]=(x*(x-1))//2

S=0
for k in E:
    S+=E[k]

for i in range(N):
    print(S-(D[A[i]]-1))
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))

def bools(b):
    if b==True:
        return 1
    else:
        return 0

def m(x,y):
    if (x,y)==(W-1,H-1):
        return 0
    elif x==W-1:
        return m(x,y+1)+bools(S[y][x]!=S[y+1][x])
    
    elif y==H-1:
        return m(x+1,y)+bools(S[y][x]!=S[y][x+1])

    else:
        return min(m(x+1,y)+bools(S[y][x]!=S[y][x+1]),m(x,y+1)+bools(S[y][x]!=S[y+1][x]))

print((m(0,0)+bools(S[0][0]==0)+1)//2)


Fixed submission:
H,W=map(int,input().split())

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))


Z=[[0]*W for i in range(H)]

for y in range(H):
    if y==0:
        for x in range(W):
            if x==0:
                Z[0][0]=1-S[0][0]
            else:
                Z[y][x]=Z[y][x-1]+(S[y][x-1]==1 and S[y][x]==0)
    else:
        for x in range(W):
            if x==0:
                Z[y][x]=Z[y-1][x]+(S[y-1][x]==1 and S[y][x]==0)
            else:
                Z[y][x]=min(Z[y][x-1]+(S[y][x-1]==1 and S[y][x]==0),Z[y-1][x]+(S[y-1][x]==1 and S[y][x]==0))

print(Z[H-1][W-1])

Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))

def m(x,y):
    if (x,y)==(W-1,H-1):
        return 0
    elif x==W-1:
        if S[y][x]==1 and S[y+1][x]==0:
            return m(x,y+1)+1
        else:
            return m(x,y+1)
    
    elif y==H-1:
        if S[y][x]==1 and S[y][x+1]==0:
            return m(x+1,y)+1
        else:
            return m(x+1,y)

    else:
        v=m(x+1,y)
        u=m(x,y+1)
        
        s=S[y][x]
        if s==1 and S[y][x+1]==0:
            v+=1
        if s==1 and S[y+1][x]==0:
            u+=1

        return min(u,v)

print(m(0,0)+1-S[0][0])


Fixed submission:
H,W=map(int,input().split())

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))


Z=[[0]*W for i in range(H)]

for y in range(H):
    if y==0:
        for x in range(W):
            if x==0:
                Z[0][0]=1-S[0][0]
            else:
                Z[y][x]=Z[y][x-1]+(S[y][x-1]==1 and S[y][x]==0)
    else:
        for x in range(W):
            if x==0:
                Z[y][x]=Z[y-1][x]+(S[y-1][x]==1 and S[y][x]==0)
            else:
                Z[y][x]=min(Z[y][x-1]+(S[y][x-1]==1 and S[y][x]==0),Z[y-1][x]+(S[y-1][x]==1 and S[y][x]==0))

print(Z[H-1][W-1])
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
reverse=False

A,B="",""
for _ in range(Q):
    T=input()
    if T[0]=="1":
        reverse=not reverse
    else:
        _,F,C=T.split()

        if ((not reverse) and F=="1") or (reverse and F=="2"):
            A+=C
        else:
            B+=C

if reverse:
    print(B[::-1]+S[::-1]+A)
else:
    print(A[::-1]+S+B)


Fixed submission:
from collections import deque
H=deque(input())
Q=int(input())
reverse=False

A,B="",""
for _ in range(Q):
    T=input()
    if T[0]=="1":
        reverse=not reverse
    else:
        _,F,C=T.split()

        if ((not reverse) and F=="1") or (reverse and F=="2"):
            H.appendleft(C)
        else:
            H.append(C)

if reverse:
    H.reverse()

for s in H:
    print(s,end="")
print()

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
reverse=False
for _ in range(Q):
    T=input()
    if T[0]=="1":
        reverse=not reverse
    else:
        _,F,C=T.split()

        if ((not reverse) and F=="1") or (reverse and F=="2"):
            S=C+S
        else:
            S=S+C

if reverse:
    print(S[::-1])
else:
    print(S)


Fixed submission:
from collections import deque
H=deque(input())
Q=int(input())
reverse=False

A,B="",""
for _ in range(Q):
    T=input()
    if T[0]=="1":
        reverse=not reverse
    else:
        _,F,C=T.split()

        if ((not reverse) and F=="1") or (reverse and F=="2"):
            H.appendleft(C)
        else:
            H.append(C)

if reverse:
    H.reverse()

for s in H:
    print(s,end="")
print()
Buggy python submission (verdict: Runtime Error):
N,M=int(input())
if N==M:
  print("Yes")
else:
  print("No")

Fixed submission:
N,M=map(int,input().split())
if N==M:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from math import gcd

def lcm(X):
    m=(X[0]*X[1])//gcd(X[0],X[1])

    for i in range(2,len(X)):
        g=gcd(m,X[i])
        m=(m*X[i])//g
    return m


N=map(int,input().split())
A=list(map(int,input().split()))
Mod=10**9+7

M=lcm(A)
K=0
for a in A:
    K+=M//a
    K%=Mod
print(K)

Fixed submission:
from math import gcd

def mod_prod(X,M):
    c=1
    for x in X:
        c*=x
        c%=M
    return c

N=int(input())
A=list(map(int,input().split()))
Mod=10**9+7

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

P=mod_prod(E,Mod)

Q=0
for a in A:
    Q+=pow(a,Mod-2,Mod)
    Q%=Mod
print((P*Q)%Mod)