Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    # dp[i, j]: i枚目まで投げて、表がj枚出る確率
    # dp[i, j] = dp[i-1, j-1] * p[j] + dp[i, j-1] * (1-p[j])
    # 2000x(N//2)のテーブルを作るとTLEするので、圧縮して解く
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = 0.0
    for i in range(1, N+1):
        b = i % 2
        for j in range(i):
            dp[b][j] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        if i > N//2:
            ans += dp[b][-1]
    return "{:.10f}".format(ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Fixed submission:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    # dp[i, j]: i枚目まで投げて、表がj枚出る確率
    # dp[i, j] = dp[i-1, j-1] * p[j] + dp[i, j-1] * (1-p[j])
    # 2000x(N//2)のテーブルを作るとTLEするので、圧縮して解く
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = dp[0][-1]
    for i in range(1, N//2+1):
        b = i % 2
        dp[b][i-1] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        ans += dp[b][-1]
    return "{:.10f}".format(1.0 - ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Buggy python submission (verdict: Runtime Error):
def read():
    N, H, W = list(map(int, input().strip().split()))
    A = []
    B = []
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return N, H, W, A, B


def solve(N, H, W, A, B):
    count = 0
    for i in range(N):
        if A[i] >= H and B[i] >= W:
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    print(solve(inputs))


Fixed submission:
def read():
    N, H, W = list(map(int, input().strip().split()))
    A = []
    B = []
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return N, H, W, A, B


def solve(N, H, W, A, B):
    count = 0
    for i in range(N):
        if A[i] >= H and B[i] >= W:
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
Buggy python submission (verdict: Time Limit Exceeded):
import math


def read():
    N, P = list(map(int, input().strip().split()))
    return N, P


def solve(N, P):
    v3 = math.floor(P**(1/N)) + 1
    for v in range(v3, 0, -1):
        if P % (v**N) == 0:
            return v
    return 1


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


Fixed submission:
import math


def read():
    N, P = list(map(int, input().strip().split()))
    return N, P


def solve(N, P):
    # problem constraint
    if N >= 40:
        return 1
    # solve
    v3 = math.floor(P**(1/N)) + 1
    for v in range(v3, 0, -1):
        if P % (v**N) == 0:
            return v
    return 1


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def read():
    S = list(input().strip())
    return S,

def solve(S):
    N = len(S)
    count = 0
    l = 0
    r = N-1
    while S[r] != 'W':
        r-=1
    s = list()
    c = 0
    for i in range(r, -1, -1):
        d = r - i
        if S[i] == 'B':
            s.append(d - c)
            c += 1
    return sum(s)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


Fixed submission:
import sys
input = sys.stdin.readline


def read():
    S = list(input().strip())
    return S,

def solve(S):
    N = len(S)
    count = 0
    l = 0
    r = N-1
    while r >= 0 and S[r] != 'W':
        r-=1
    s = list()
    c = 0
    for i in range(r, -1, -1):
        d = r - i
        if S[i] == 'B':
            s.append(d - c)
            c += 1
    return sum(s)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def read():
    H, W = map(int, input().strip().split())
    S = []
    for i in range(H):
        s = list(input().strip())
        S.append(s)
    return H, W, S


def solve(H, W, S):
    dd = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def dfs(y, x):
        depth = 0
        S[y][x] = "."
        for dy, dx in dd:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "#":
                depth = max(depth, dfs(ny, nx) + 1)
        return depth

    for i in range(H):
        for j in range(W):
            depth = dfs(i, j)
            if depth == 1:
                return "No"
    return "Yes"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def read():
    H, W = map(int, input().strip().split())
    S = []
    for i in range(H):
        s = list(input().strip())
        S.append(s)
    return H, W, S


def solve(H, W, S):
    if H == 1 and  W == 1 and S[0][0] == "#":
        return "No"
    
    dd = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def dfs(y, x):
        depth = 1
        S[y][x] = "."
        for dy, dx in dd:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "#":
                depth = max(depth, dfs(ny, nx) + 1)
        return depth

    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                depth = dfs(i, j)
                if depth == 1:
                    return "No"
    return "Yes"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    CSF = []
    for i in range(N-1):
        c, s, f = map(int, input().strip().split())
        CSF.append((c, s, f))
    return N, CSF


def solve(N, CSF, SMAX=200000):
    dp = [[0 for t in range(SMAX)] for i in range(N)]
    for i in range(N):
        dp[i][0] = 1
    for i in range(N-1):
        c, s, f = CSF[i]
        for t in range(s, SMAX-c, f):
            if t == s:
                dp[i+1][t+c] = sum(dp[i][:t+1])
            else:
                dp[i+1][t+c] = sum(dp[i][t-f+1:t+1])
    ans = []
    for t in range(SMAX):
        while dp[N-1][t] > 0:
            ans.append(t)
            dp[N-1][t] -= 1
    for a in ans[::-1]:
        print(a)



if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    CSF = []
    for i in range(N-1):
        c, s, f = map(int, input().strip().split())
        CSF.append((c, s, f))
    return N, CSF


def solve(N, CSF, SMAX=200000):
    A = []
    for c, s, f in CSF:
        for i in range(len(A)):
            if A[i] % f == 0:
                A[i] = max(A[i], s) + c
            else:
                A[i] = max(A[i] - A[i] % f + f, s) + c
        A.append(s + c)
    A.append(0)
    for a in A:
        print(a)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline

s=int(input())

INF=10**9+7

def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m

ans=0
for n in range(1,667):
    if s-3*n>=0:
        ans=(ans+modcomb(s-2*n-1,n-1,INF))%INF

print(ans)

Fixed submission:
import sys
input=sys.stdin.readline

s=int(input())

INF=10**9+7

def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m

ans=0
if s==3:
    ans=1
else:
    for n in range(1,667):
        if s-3*n>=0:
            ans=(ans+modcomb(s-2*n-1,n-1,INF))%INF

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
D=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(D):
    sub=list(map(int,input().split()))
    s.append(sub)

last=[-1]*26

t=[]

for i in range(D):
    m=-10**9
    change=-1
    for j in range(26):
        temp=0
        temp+=s[i][j]
        for k in range(26):
            if k!=j:
                temp-=c[k]*(i-last[k])
        if temp>m:
            m=temp
            change=j
    t.append(change+1)

m=3000000
import random
for _ in range(m):
    h=0
    d=random.randint(1,D)
    q=random.randint(1,26)
    h+=s[d-1][q-1]-s[d-1][t[d-1]-1]
    o=t[d-1]

    pre=1
    for i in range(d-2,-1,-1):
        if t[i]==o:
            break
        pre+=1
    post=1
    for j in range(d,D):
        if t[j]==o:
            break
        post+=1
    h-=c[o-1]*pre*post

    pre = 1
    for i in range(d - 2, -1, -1):
        if t[i] == q:
            break
        pre += 1
    post = 1
    for j in range(d, D):
        if t[j] == q:
            break
        post += 1
    h += c[q - 1] * pre * post

    if h>0:
        t[d-1]=q

for i in t:
    print(i)

Fixed submission:
import sys
input=sys.stdin.readline
d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
    sub=list(map(int,input().split()))
    s.append(sub)

last=[-1]*26

for i in range(d):
    m=-10**9
    change=-1
    for j in range(26):
        temp=0
        temp+=s[i][j]
        for k in range(26):
            if k!=j:
                temp-=c[k]+(i-last[k])
        if temp>m:
            m=temp
            change=j
    print(change+1)
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
if p==2:
    for i in range(n):
        ans=0
        if s[i]%2==0:
            ans+=i+1
elif p==5:
    for i in range(n):
        ans=0
        if s[i]==0 or s[i]==5:
            ans+=i+1
else:
    count=[0]*p
    x=0
    y=1
    count[0]=1
    for i in range(n-1,-1,-1):
        x=x+y*int(s[i])
        x=x%p
        count[x]+=1
        y=(y*10)%p
    ans=0
    for i in count:
        ans+=i*(i-1)//2
print(ans)



Fixed submission:
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
if p==2:
    ans=0
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
elif p==5:
    ans=0
    for i in range(n):
        if int(s[i])==0 or int(s[i])==5:
            ans+=i+1
else:
    count=[0]*p
    x=0
    y=1
    count[0]=1
    for i in range(n-1,-1,-1):
        x=x+y*int(s[i])
        x=x%p
        count[x]+=1
        y=(y*10)%p
    ans=0
    for i in count:
        ans+=i*(i-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
INF=10**9+7
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
ans=0
ans=(ans-modcomb(n,a,INF)-modcomb(n,b,INF))%INF
ans=(ans+pow(2,n,INF)-1)%INF
print(ans)





Fixed submission:
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
INF=10**9+7
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
ans=(ans+pow(2,n,INF)-1)%INF
bunsi=1
bunbo=1
for i in range(a):
    bunsi=(bunsi*(n-i))%INF
    bunbo=(bunbo*(i+1))%INF
x=(bunsi*modinv(bunbo,INF))%INF
bunsi=1
bunbo=1
for i in range(b):
    bunsi=(bunsi*(n-i))%INF
    bunbo=(bunbo*(i+1))%INF
y=(bunsi*modinv(bunbo,INF))%INF
ans=(ans-x-y)%INF
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
n=int(input())
ans=0
ns=str(n)
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)








Fixed submission:
import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
n=int(input())
ans=0
ns=str(n)
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)








Fixed submission:
import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
n=int(input())
ans=0
l=[]
for _ in range(10**6+1):
    x=n%10
    l.append(x)
    n=(n-x)//10
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)








Fixed submission:
import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
A=[]
for i in range(h):
    a_list=list(map(int,input().split()))
    A.append(a_list)
B=[]
for i in range(h):
    b_list=list(map(int,input().split()))
    B.append(b_list)
dp=[set() for i in range(w)]
dp[0].add(0)
for i in range(h):
    for j in range(w):
        s=set()
        for x in dp[j]:
            y=abs(x+(A[i][j]-B[i][j]))
            z=abs(x+(B[i][j]-A[i][j]))
            s.add(y)
            s.add(z)
        dp[j]=s
        if j<w-1:
            dp[j+1]=s|dp[j+1]
ans=min(dp[w-1])
print(ans)        
    


Fixed submission:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
A=[]
for i in range(h):
    a_list=list(map(int,input().split()))
    A.append(a_list)
B=[]
for i in range(h):
    b_list=list(map(int,input().split()))
    B.append(b_list)
dp=[]
for i in range(w):
    sub_list=[False]*12802
    dp.append(sub_list)
dp[0][0]=True
for i in range(h):
    for j in range(w):
        c=A[i][j]-B[i][j]
        l=[False]*12802
        for x in range(12802):
            if dp[j][x]:
                l[abs(x+c)]=True
                l[abs(x-c)]=True
                if j<w-1:
                    dp[j+1][abs(x+c)]=True
                    dp[j+1][abs(x-c)]=True
        dp[j]=l
ans=20000
for x in range(12802):
    if dp[w-1][x]:
        ans=min(ans,x)
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
c1=[0]
c2=[k]
s=0
if n==1:
    ans=0
    if a[0]%k==1:
        ans+=1
    print(ans)
    sys.exit()
for i in range(n):
    s=(s+a[i])%k
    c1.append(s-i-1)
    c2.append(s+k-i-1)
d1={}
for i in range(1,n+1):
    if c1[i] in d1:
        d1[c1[i]]+=1
    else:
        d1[c1[i]]=1
ans=0
for i in range(n):
    if c1[i] in d1:
        ans+=d1[c1[i]]
    d1[c1[i+1]]-=1
d2={}
for i in range(1,min(k,n+1)):
    if c2[i] in d2:
        d2[c2[i]]+=1
    else:
        d2[c2[i]]=1
for i in range(n):
    if c1[i] in d2:
        ans+=d2[c1[i]]
    d2[c2[i+1]]-=1
    if i+k<=n:
        if c2[i+k] in d2:
            d2[c2[i+k]]+=1
        else:
            d2[c2[i+k]]=1
print(ans)










Fixed submission:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
c1=[0]
c2=[k]
s=0
if k==1:
    print(0)
    sys.exit()
for i in range(n):
    s=(s+a[i])%k
    c1.append(s-i-1)
    c2.append(s+k-i-1)
d1={}
for i in range(1,n+1):
    if c1[i] in d1:
        d1[c1[i]]+=1
    else:
        d1[c1[i]]=1
ans=0
for i in range(n):
    if c1[i] in d1:
        ans+=d1[c1[i]]
    d1[c1[i+1]]-=1
d2={}
for i in range(1,min(k,n+1)):
    if c2[i] in d2:
        d2[c2[i]]+=1
    else:
        d2[c2[i]]=1
for i in range(n):
    if c1[i] in d2:
        ans+=d2[c1[i]]
    d2[c2[i+1]]-=1
    if i+k<=n:
        if c2[i+k] in d2:
            d2[c2[i+k]]+=1
        else:
            d2[c2[i+k]]=1
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
c1=[0]
c2=[k]
s=0
for i in range(n):
    s=(s+a[i])%k
    c1.append(s-i-1)
    c2.append(s+k-i-1)
d1={}
for i in range(1,n+1):
    if c1[i] in d1:
        d1[c1[i]]+=1
    else:
        d1[c1[i]]=1
ans=0
for i in range(n):
    if c1[i] in d1:
        ans+=d1[c1[i]]
    d1[c1[i+1]]-=1
d2={}
for i in range(1,min(k,n+1)):
    if c2[i] in d2:
        d2[c2[i]]+=1
    else:
        d2[c2[i]]=1
for i in range(n):
    if c1[i] in d2:
        ans+=d2[c1[i]]
    d2[c2[i+1]]-=1
    if i+k<=n:
        if c2[i+k] in d2:
            d2[c2[i+k]]+=1
        else:
            d2[c2[i+k]]=1
print(ans)










Fixed submission:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
c1=[0]
c2=[k]
s=0
if k==1:
    print(0)
    sys.exit()
for i in range(n):
    s=(s+a[i])%k
    c1.append(s-i-1)
    c2.append(s+k-i-1)
d1={}
for i in range(1,n+1):
    if c1[i] in d1:
        d1[c1[i]]+=1
    else:
        d1[c1[i]]=1
ans=0
for i in range(n):
    if c1[i] in d1:
        ans+=d1[c1[i]]
    d1[c1[i+1]]-=1
d2={}
for i in range(1,min(k,n+1)):
    if c2[i] in d2:
        d2[c2[i]]+=1
    else:
        d2[c2[i]]=1
for i in range(n):
    if c1[i] in d2:
        ans+=d2[c1[i]]
    d2[c2[i+1]]-=1
    if i+k<=n:
        if c2[i+k] in d2:
            d2[c2[i+k]]+=1
        else:
            d2[c2[i+k]]=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a_list=list(map(int,input().split()))
count=0
for i in range(n):
    if i%2==0:
        count+=a_list[i]
    else:
        count-=a_list[i]
ans=''
ans=ans+str(count)
now=count//2
for i in range(n-1):
    now=a_list[i]-now
    ans=ans+' '+str(now*2)
print(ans)
            


Fixed submission:
n=int(input())
a_list=list(map(int,input().split()))
count=0
for i in range(n):
    if i%2==0:
        count+=a_list[i]
    else:
        count-=a_list[i]
print(count,end='')
now=count//2
for i in range(n-1):
    now=a_list[i]-now
    print(' ',end='')
    print(now*2,end='')
Buggy python submission (verdict: Time Limit Exceeded):
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
def dfs(x):
    global ans
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            dfs(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
dfs(0)
print((ans*k)%INF)
        


Fixed submission:
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
stack=[0]
ans=1
while len(stack)>0:
    x=stack.pop()
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            stack.append(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
print((ans*k)%INF)

Buggy python submission (verdict: Runtime Error):
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
def dfs(x):
    global ans
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            dfs(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
dfs(0)
print((ans*k)%INF)
        


Fixed submission:
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
stack=[0]
ans=1
while len(stack)>0:
    x=stack.pop()
    check[x]=True
    count=0
    for i in graph[x]:
        if not check[i]:
            count+=1
            stack.append(i)
    if x==0:
        temp=1
        for i in range(count):
            temp=temp*(k-1-i)%INF
        ans=ans*temp%INF
    else:
        temp=1
        for i in range(count):
            temp=temp*(k-2-i)%INF
        ans=ans*temp%INF
print((ans*k)%INF)