Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
mod=10**9+7
a=[]
for i in range(M):
    a.append(int(input()))


DP=[1]*(N+1)

if 1 in a:
    DP[1]=0

for i in range(2,N+1):
    if i in a:
        DP[i]=0
        if DP[i-1]==0:
            print(0)
            exit()
    else:
        DP[i]=DP[i-1]+DP[i-2]
        DP[i]=DP[i]%mod

print(DP[N])


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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())
    chk[a]=False

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)
f[0]=1
if chk[1]:
    f[1]=1
else:
    f[1]=0


for i in range(2,N+1):
    if chk[i-2]:
        f[i]+=f[i-2]
    if chk[i-1]:
        f[i]+=f[i-1]
    f[i]=f[i]%mod

print(f[N])

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
a=[int(input())-1 for i in range(M)]

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)

if 0 in a:
    f[0]=0
else:
    f[0]=1

if 1 in a:
    f[1]=0
else:
    f[1]=f[0]+1

for i in range(2,N):
    if i in a:
        f[i]=0
    else:
        f[i]=f[i-2]+f[i-1]

    f[i]=f[i]%mod

print(f[N-1])

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())
    chk[a]=False

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)
f[0]=1
if chk[1]:
    f[1]=1
else:
    f[1]=0


for i in range(2,N+1):
    if chk[i-2]:
        f[i]+=f[i-2]
    if chk[i-1]:
        f[i]+=f[i-1]
    f[i]=f[i]%mod

print(f[N])
Buggy python submission (verdict: Runtime Error):
N,A,B,C,D=map(int,input().split())
A=A-1
B=B-1
C=C-1
D=D-1

s=input()

if C<D:
    if not "##" in s[A:D+1]:
        ans="Yes"
    else:
        ans="No"
elif D<C:
    if not "##" in s[A:C+1]:
        if "..." in s[B-1:D+1]:
            ans="Yes"
    else:
        ans="No"

print(ans)



Fixed submission:
N,A,B,C,D=map(int,input().split())
A=A-1
B=B-1
C=C-1
D=D-1

s=input()

if A<B<C<D:
    if not "##" in s[B:D+1]:
        if not "##" in s[A:C+1]:
            ans="Yes"
        else:
            ans="No"
    else:
        ans="No"
elif A<B<D<C:
    if not "##" in s[A:C+1]:
        if s[B-1]!="#" and s[B+1]!="#":
            ans="Yes"
        elif "..." in s[B:D+1]:
            ans="Yes"
        elif s[D-1]!="#" and s[D+1]!="#":
            ans="Yes"
        else:
            ans="No"
    else:
        ans="No"
elif A<C<B<D:
    if "##" in s[A:C+1] or "##" in s[B:D+1]:
        ans="No"
    else:
        ans="Yes"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())

N=len(s)

f=True
cnt=0
while f:
    f=False
    for i in range(2,N):
        if "".join(s[i-2:i+1])=="ABC":
            s[i-2]="B"
            s[i-1]="C"
            s[i]="A"
            cnt+=1
            f=True
print(cnt)


Fixed submission:
so=input()

s=""

N=len(so)
i=0
while i<N:
    if so[i]=="A":
        s=s+"A"
        i+=1
    elif so[i:i+2]=="BC":
        s=s+"B"
        i+=2
    elif so[i]=="C" or so[i]=="B":
        s=s+"D"
        i+=1

L=len(s)
f=False
cnt=0
a=0
for i in range(L):
    if s[i]=="A":
        f=True
        a+=1
    elif f and s[i]=="B":
        cnt+=a
    elif s[i]=="D":
        f=False
        a=0
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())

N=len(s)

f=True
cnt=0
while f:
    f=False
    for i in range(2,N):
        if "".join(s[i-2:i+1])=="ABC":
            s[i-2]="B"
            s[i-1]="C"
            s[i]="A"
            cnt+=1
            f=True
print(cnt)

Fixed submission:
so=input()

s=""

N=len(so)
i=0
while i<N:
    if so[i]=="A":
        s=s+"A"
        i+=1
    elif so[i:i+2]=="BC":
        s=s+"B"
        i+=2
    elif so[i]=="C" or so[i]=="B":
        s=s+"D"
        i+=1

L=len(s)
f=False
cnt=0
a=0
for i in range(L):
    if s[i]=="A":
        f=True
        a+=1
    elif f and s[i]=="B":
        cnt+=a
    elif s[i]=="D":
        f=False
        a=0
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

num = list(range(N))
pmax = 0

for i in range(N):
    combi = list(combinations(num,i))
    for j in range(len(combi)):
        v_value = 0
        c_value = 0
        for k in range(len(combi[j])):
            v_value = v_value + V[combi[j][k]]
            c_value = c_value + C[combi[j][k]]
            pmax = max(pmax,v_value-c_value)
 
print(pmax)


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

ans = 0

for i in range(N):
    a = V[i] - C[i]
    if a > 0:
        ans += a

print(ans)
Buggy python submission (verdict: Runtime Error):
b = input()

if b == "A":
    print("T")
elif b == "T":
    prnt("A")
elif b == "C":
    print("G")
else:
    print("C")

Fixed submission:
b = input()
if b == "A":
    print("T")
elif b == "T":
    print("A")
elif b == "C":
    print("G")
else:
    print("C")
Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()
C=[0]*N

for i in range(1,N):
    if S[i-1:i+1]=="AC":
        C[i]+=1

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



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

for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i + 1] = SC[i] + 1
    else:
        SC[i + 1] = SC[i]

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

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
SC = [0] * (N - 1)
for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i] = 1

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

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

for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i + 1] = SC[i] + 1
    else:
        SC[i + 1] = SC[i]

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

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
SC = [0] * (N - 1)
for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i] = 1

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


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

for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i + 1] = SC[i] + 1
    else:
        SC[i + 1] = SC[i]

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

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()

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

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

for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i + 1] = SC[i] + 1
    else:
        SC[i + 1] = SC[i]

for i in range(Q):
    l, r = map(int, input().split())
    print(SC[r - 1] - SC[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
A,B=map(int,input().split())

S=B-A

n=len(bin(S))-2

T=2**n

newA=A+(S//T)*T

x=newA

for i in range(newA+1,B+1):
    x=x^i

print(x)

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

a=A%4
b=B%4

ans=0
cnt=0
for i in range(a,4):
    ans=ans^(A+cnt)
    cnt+=1
cnt=0
for i in range(b,-1,-1):
    ans=ans^(B-cnt)
    cnt+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())

X=list(map(int,input().split()))
X.sort()
di=[]


for i in range(M-1):
    di.append(X[i+1]-X[i])
if N==1:
    print(sum[di])
di.sort()
print(sum(di[:M-N]))

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

X=list(map(int,input().split()))
X.sort()
di=[]

for i in range(M-1):
    di.append(X[i+1]-X[i])

di.sort(reverse=True)
print(sum(di[N-1:]))
Buggy python submission (verdict: Runtime Error):
N=int(input())
h=list(map(int,input().split()))

mi=min(h)
h0=h[0]
c=h0-mi
ans=mi
for i in range(1,N):
    if h0<h[i]:
        c+=h[i]-h0
    elif h0>h[i]:
        ans+=c
        mi = min(h[i:])
        c=h[i]-mi
    h0=h[i]

if h[-2]<h[-1]:
    ans+=c
print(ans)


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

if N==1:
    print(h[0])
    exit()

mi=min(h)
p=0
h0=h[0]
c=h0-mi
ans=mi+h0
for i in range(1,N):
    if h0<h[i]:
        c+=h[i]-h0
    elif h0>h[i]:
        c=h0-min(h[p:i])
        ans+=c
        p = i
        c=h[i]-mi
    h0=h[i]

ans+=c-min(h[p:])
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)


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

INF=float("inf")

DP=[INF]*(N+1)

def rec(n):
    if DP[n]<INF: return DP[n]
    if n==0:
        return 0
    ans=INF
    ans=min(ans,rec(n-1)+abs(h[n]-h[n-1]))
    if n>1:
        ans=min(ans,rec(n-2)+abs(h[n]-h[n-2]))
    DP[n]=ans

    return DP[n]

ans=rec(N-1)
print(ans)


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

DP=[100000]*N

DP[0]=0
DP[1]=abs(h[1]-h[0])

for i in range(2,N):
    DP[i]=min(DP[i-2]+abs(h[i]-h[i-2]),DP[i-1]+abs(h[i]-h[i-1]))

print(DP[N-1])

Buggy python submission (verdict: Runtime Error):

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

INF=float("inf")

DP=[INF]*(N+1)

def rec(n):
    if DP[n]<INF: return DP[n]
    if n==0:
        return 0
    ans=INF
    ans=min(ans,rec(n-1)+abs(h[n]-h[n-1]))
    if n>1:
        ans=min(ans,rec(n-2)+abs(h[n]-h[n-2]))
    DP[n]=ans

    return DP[n]

ans=rec(N-1)
print(ans)


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

DP=[100000]*N

DP[0]=0
DP[1]=abs(h[1]-h[0])

for i in range(2,N):
    DP[i]=min(DP[i-2]+abs(h[i]-h[i-2]),DP[i-1]+abs(h[i]-h[i-1]))

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

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

for i in range(N):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w>=0:
            DP[i+1][j]=max(DP[i][j],DP[i][j-w]+v)
        DP[i+1][j]=max(DP[i+1][j],DP[i][j])
print(max(DP[N]))



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

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

for i in range(N):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w>=0:
            DP[i+1][j]=max(DP[i][j],DP[i][j-w]+v)
        DP[i+1][j]=max(DP[i+1][j],DP[i][j])
print(max(DP[N]))
Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w=[]
v=[]

for i in range(N):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

S=sum(v)

DP=[[1000000000000]*(S+1) for i in range(N+1)]
for i in range(N+1):
    DP[i][0]=0



for i in range(N):
    for v1 in range(S+1):
        DP[i+1][v1]=min(DP[i][v1-v[i]]+w[i],DP[i][v1])

for i in range(S,0,-1):
    if DP[N][i]<=W:
        print(i)
        exit()

Fixed submission:
N,W=map(int,input().split())
w=[]
v=[]

for i in range(N):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

S=sum(v)

DP=[[1000000000000]*(S+1) for i in range(N+1)]
for i in range(N+1):
    DP[i][0]=0



for i in range(N):
    for v1 in range(S+1):
        DP[i+1][v1]=min(DP[i][v1-v[i]]+w[i],DP[i][v1])

for i in range(S,0,-1):
    if DP[N][i]<=W:
        print(i)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
p=list(map(float,input().split()))

DP=[[0]*(N+1) for _ in range(N)]

DP[0][0]=1-p[0]
DP[0][1]=p[0]
for i in range(1,N):
    for j in range(i+2):
        if j==0:
            DP[i][j]=DP[i-1][j]*(1-p[i])
        else:
            DP[i][j]=DP[i-1][j-1]*p[i]+DP[i-1][j]*(1-p[i])
ans=sum(DP[N-1][(N+1)//2:])

print(ans)

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

DP=[[0]*(N+1) for _ in range(N)]

DP[0][0]=1-p[0]
DP[0][1]=p[0]
for i in range(1,N):
    for j in range(i+2):
        if j==0:
            DP[i][j]=DP[i-1][j]*(1-p[i])
        else:
            DP[i][j]=DP[i-1][j-1]*p[i]+DP[i-1][j]*(1-p[i])
ans=sum(DP[N-1][(N+1)//2:])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

if N ==1:
    print(P)
    exit()
 

q = math.floor(math.sqrt(P))+1

ans = 1

for i in range(2,q+1):
    a = i**N
    if P%a == 0:
        ans = i
        
print(ans)

Fixed submission:

N,P=map(int,input().split())
if N==1:
    print(P)
    exit()
elif P==1:
    print(1)
    exit()

PO=P
K=[0]*(int(P**0.5)+1)

for i in range(2,int(P**0.5)):
    while P%i==0:
        K[i]+=1
        P=P//i
    K[i]=K[i]//N
    if P==1:
        break

ans=1
for i in range(2,int(PO**0.5)):
    if K[i]!=0:
        ans*=i**K[i]

print(ans)

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

if N ==1:
    print(P)
    exit()
 
i=1
a = i**N
 
while a<=P:
    if P%a == 0:
        ans = i
    i = i+1
    a = i**N
    
print(ans)

Fixed submission:

N,P=map(int,input().split())
if N==1:
    print(P)
    exit()
elif P==1:
    print(1)
    exit()

PO=P
K=[0]*(int(P**0.5)+1)

for i in range(2,int(P**0.5)):
    while P%i==0:
        K[i]+=1
        P=P//i
    K[i]=K[i]//N
    if P==1:
        break

ans=1
for i in range(2,int(PO**0.5)):
    if K[i]!=0:
        ans*=i**K[i]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

N,P = map(int,input().split())
k =[0]*3
i = 2
P0 = P

while P0 != 1:
    while P0%i == 0:
        k[i]=k[i]+1
        P0 = P0//i
       
    i = i+1
    k.append(0)

g =1

for j in range(2,i):
    k[j] = k[j]//N
    g = g * j ** k[j]

print(g)


Fixed submission:

N,P=map(int,input().split())
if N==1:
    print(P)
    exit()
elif P==1:
    print(1)
    exit()

PO=P
K=[0]*(int(P**0.5)+1)

for i in range(2,int(P**0.5)):
    while P%i==0:
        K[i]+=1
        P=P//i
    K[i]=K[i]//N
    if P==1:
        break

ans=1
for i in range(2,int(PO**0.5)):
    if K[i]!=0:
        ans*=i**K[i]

print(ans)

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

i=1
a = i**N

while a<=P:
    if P%a == 0:
        ans = i
    i = i+1
    a = i**N
    
print(ans)

Fixed submission:

N,P=map(int,input().split())
if N==1:
    print(P)
    exit()
elif P==1:
    print(1)
    exit()

PO=P
K=[0]*(int(P**0.5)+1)

for i in range(2,int(P**0.5)):
    while P%i==0:
        K[i]+=1
        P=P//i
    K[i]=K[i]//N
    if P==1:
        break

ans=1
for i in range(2,int(PO**0.5)):
    if K[i]!=0:
        ans*=i**K[i]

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
p = [0]*N
s = 0

for i in range(N):
   p[i] = int(input())
   s = s + p[i]
   
print(s-max(p)//2)
    


Fixed submission:
D = int(input())

print("Christmas" + " Eve" * (25-D))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

A=[int(input()) for i in range(N)]

A.sort()

ans=[A[0],A[-1]]
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ans[0])
    n[1]=abs(A[l]-ans[-1])
    n[2]=abs(A[r]-ans[0])
    n[3]=abs(A[r]-ans[-1])
    if n[0]==max(n):
        ansn+=n[0]
        ans.insert(0,A[l])
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ans.insert(len(ans),A[l])
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ans.insert(0,A[r])
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ans.insert(len(ans),A[r])
        r-=1

print(ansn)

Fixed submission:
N=int(input())

A=[int(input()) for i in range(N)]

A.sort()

ansl=A[0]
ansr=A[-1]
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ansl)
    n[1]=abs(A[l]-ansr)
    n[2]=abs(A[r]-ansl)
    n[3]=abs(A[r]-ansr)
    if n[0]==max(n):
        ansn+=n[0]
        ansl=A[l]
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ansr=A[l]
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ansl=A[r]
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ansr=A[r]
        r-=1

print(ansn)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

for i in range(N,M+1):
    if M%i==0:
        print(M//i)
        exit()

Fixed submission:
N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

if N>=M**0.5:
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            exit()
else:
    for i in range(N,M+1):
        if M%i==0:
            print(M//i)
            exit()
print(1)

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

for i in range(N,M+1):
    if M%i==0:
        print(M//i)
        exit()

Fixed submission:
N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

if N>=M**0.5:
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            exit()
else:
    for i in range(N,M+1):
        if M%i==0:
            print(M//i)
            exit()
print(1)

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

for i in range(N,M+1):
    if M%i==0:
        print(M//i)
        exit()

Fixed submission:
N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

if N>=M**0.5:
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            exit()
else:
    for i in range(N,M+1):
        if M%i==0:
            print(M//i)
            exit()
print(1)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
c=0
if K%2==0:
    d=K//2
else:
    print((N//K)**3)
    exit()

for i in range(d,N+1,d):
    for j in range(d,N+1,d):
        for k in range(d,N+1,d):
            if (i+j)%K==0 and (j+k)%K==0 and (k+i)%K==0:
                c+=1
print(c)

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

if K%2==0:
    print((N//K)**3+((N//(K//2))-(N//K))**3)
else:
    print((N//K)**3)

Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
c=0
if K%2==0:
    d=K//2
else:
    print(N//K**3)

for i in range(d,N+1,d):
    for j in range(d,N+1,d):
        for k in range(d,N+1,d):
            if (i+j)%K==0 and (j+k)%K==0 and (k+i)%K==0:
                c+=1
print(c)

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

if K%2==0:
    print((N//K)**3+((N//(K//2))-(N//K))**3)
else:
    print((N//K)**3)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
c=0
if K%2==0:
    d=K//2
else:
    d=K

for i in range(d,N+1,d):
    for j in range(d,N+1,d):
        for k in range(d,N+1,d):
            if (i+j)%K==0 and (j+k)%K==0 and (k+i)%K==0:
                c+=1
print(c)

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

if K%2==0:
    print((N//K)**3+((N//(K//2))-(N//K))**3)
else:
    print((N//K)**3)
Buggy python submission (verdict: Runtime Error):

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

DP=[[[0]*m for _ in range(n)] for _ in range(m)]

for i in range(n):
    DP[0][i][0]=1

for i in range(1,m):
    for j in range(n):
        for k in range(m):
            if k==0:
                if j-d<0:
                    DP[i][j][k]=DP[i-1][j+d][0]
                elif j+d>=n:
                    DP[i][j][k]=DP[i-1][j-d][0]
                else:
                    DP[i][j][k]=DP[i-1][j+d][0]+DP[i-1][j+d][0]
            else:
                if j-d<0:
                    DP[i][j][k]=DP[i-1][j+d][k-1]+DP[i-1][j][k]
                elif j+d>=n:
                    DP[i][j][k]=DP[i-1][j-d][k-1]+DP[i-1][j][k]
                else:
                    DP[i][j][k]=DP[i-1][j+d][k-1]+DP[i-1][j-d][k-1]+DP[i-1][j][k]
            DP[i][j][k]=DP[i][j][k]/n

ans=0
for i in range(n):
    for j in range(1,m):
        ans+=DP[m-1][i][j]*j
ans=ans/n
print(ans)



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

if d==0:
    ans=(m-1)/n
else:
    ans=(n-d)*2*(m-1)/(n*n)

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

i = 0
s = 0

for i in range(1, b - a):
    s += i
print(s - a)

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

i = 0
s = 0

for i in range(1, b - a):
    s += i
print(s - a)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
K=int(input())

S=[]
for n in range(1,len(s)+1):
    for i in range(len(s)-n+1):
        S.append(s[i:i+n])
S=list(set(S))
S.sort()

print(S[K-1])



Fixed submission:
s=input()
K=int(input())

S=[]
for n in range(len(s)):
    for i in range(1,len(s)-n+1):
        if len(S)<5:
            S.append(s[n:i+n])
            S = list(set(S))
            S.sort()
        elif S[4]>s[n:i+n]:
            S.append(s[n:i+n])
            S = list(set(S))
            S.sort()
        else:
            break
S=list(set(S))
S.sort()

print(S[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

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

cnt=0
for i in range(N):
    for j in range(i,N):
        if sum(A[i:j+1])==0:
            cnt+=1
print(cnt)


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

S=[]
temp=0
for i in range(N):
    temp=temp+A[i]
    S.append(temp)

from collections import Counter

cnt=Counter(S)

ans=0
for c in cnt.values():
    ans+=c*(c-1)//2

if cnt[0]!=0:
    ans+=cnt[0]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial

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

a.sort()

ai=a[n-1]

a0=factorial(ai)//(factorial(ai-a[0])*factorial(a[0]))


for i in range(1,n-1):
    j=a[i]
    temp=a0
    for k in range(1,a[i]-a[i-1]+1):
        temp*=(ai-(a[i-1]+k-1))/(a[i-1]+k)

    if a0>=temp:
        print(str(ai)+" "+str(a[i-1]))
        exit()
    a0=temp

print(str(ai)+" "+str(a[n-2]))





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

ans1=a[0]

b=ans1//2
ans2=0
for i in range(n):
    if abs(a[i]-b)<abs(ans2-b):
        ans2=a[i]

print(ans1,ans2)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())

ans=0
for k in range(K,N):
    if k==0:
        for i in range(1,N+1):
            if N//i==1:
                ans+=N-(i-1)
                break
            else:
                ans+=N//i
    else:
        for i in range(k+1,N+1):
            if (N-k)//i==0:
                ans+=N-(i-1)
                break
            else:
                ans+=1+(N-k)//i
print(ans)

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

if K==0:
    print(N**2)
    exit()

ans=0
for i in range(K+1,N+1):
    ans+=N//i*(i-K)+max(0,N%i-(K-1))
print(ans)
Buggy python submission (verdict: Runtime Error):
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    return ans

N=int(input())
S=[0]*5

for i in range(N):
    s=input()
    temp=s[0]
    if temp=="M":
        S[0]+=1
    elif temp=="A":
        S[1]+=1
    elif temp=="R":
        S[2]+=1
    elif temp=="C":
        S[3]+=1
    elif temp=="H":
        S[4]+=1

c=0
N=0
for i in range(5):
    N+=S[i]
    if S[i]!=0:
        c+=1

if c<=2:
    print(0)

else:

    for i in range(5):
        if S[i]>=3:
            NG=combi(S[i],3)+combi(S[i],2)*(N-S[i])
        elif S[i]==2:
            NG=combi(S[i],2)*(N-S[i])
    print(int(combi(N,3)-NG))





Fixed submission:
import math


def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    return ans


N = int(input())
S = [0] * 5

for i in range(N):
    s = input()
    temp = s[0]
    if temp == "M":
        S[0] += 1
    elif temp == "A":
        S[1] += 1
    elif temp == "R":
        S[2] += 1
    elif temp == "C":
        S[3] += 1
    elif temp == "H":
        S[4] += 1

c = 0
N = 0
for i in range(5):
    N += S[i]
    if S[i] != 0:
        c += 1

if c <= 2:
    print(0)

else:
    ans = 0
    for i in range(3):
        for j in range(i + 1, 4):
            for k in range(j + 1, 5):
                ans += S[i] * S[j] * S[k]
    print(ans)