Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=list(map(int,input().split()))
ans=1
for i in l:
    ans*=i

if ans>1000000000000000000:print(-1)
else:print(ans)

Fixed submission:
n=int(input())
l=list(map(int,input().split()))
l.sort()
if l[0]==0:
    print(0)
    exit(0)
ans=1
for i in l:
    ans*=i
    if ans>1000000000000000000:
        print(-1)
        exit(0)
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
a = 1
L = list(map(int, input().split()))
for i in L:
    a *= i
    if(a > 1e18)break

print(-1 if a > 1e18 else a)


Fixed submission:
N = int(input())
a = 1
L = list(map(int, input().split()))
L.sort()
for i in L:
    a *= i
    if (a > 1e18):
        break

print(-1 if a > 1e18 else a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = 1
L = list(map(int, input().split()))
for i in L:
    a *= i

print(-1 if a > 1e18 else a)


Fixed submission:
N = int(input())
a = 1
L = list(map(int, input().split()))
L.sort()
for i in L:
    a *= i
    if (a > 1e18):
        break

print(-1 if a > 1e18 else a)
Buggy python submission (verdict: Runtime Error):
N=int(input())

if N%2==1:
    print(0)
else:
    ans=0
    div=10
    while N//div>0:
        ans+=N//div
        div*=5
print(ans)

Fixed submission:
N=int(input())

if N%2==1:
    print(0)
else:
    ans=0
    div=10
    while N//div>0:
        ans+=N//div
        div*=5
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-x*(x-1)*pow(2,c,mod))%mod
print(ans)

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-x*(x-1)*(2**c))%mod
print(ans)

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

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

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
X,Y=map(int,input().split())
if X<Y:
    X,Y=Y,X
mod=10**9+7

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

x,y=0,0
while X>=3 and Y>=3:
    x+=1
    y+=1
    X-=3
    Y-=3
if X==0 and Y==0:
    pass
elif X//Y == 2 and X%Y==0:
    x+=Y
else:
    print(0)
    exit()

print(Comb(x+y,y))

Fixed submission:
X,Y=map(int,input().split())
if X<Y:
    X,Y=Y,X
mod=10**9+7

N=min(X,Y)
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]%mod

d=X-Y
if (Y-d)%3!=0 or Y-d<0:
    print(0)
    exit()
x,y=d+(Y-d)//3,(Y-d)//3

print(Comb(x+y,y))
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
F=sorted(map(int,input().split()))[::-1]

left,right=-1,10**12
while left + 1 < right:
    mid = (left + right)//2
    if sum([max(0,a-mid//f) for a,f in zip(A,F)])>K:
        left = mid
    else:
        right = mid
print(right)

Fixed submission:
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
F=sorted(map(int,input().split()))[::-1]

left,right=-1,10**12
while left + 1 < right:
    mid = (left + right)//2
    if sum([max(0,a-mid//f) for a,f in zip(A,F)])>K:
        left = mid
    else:
        right = mid
print(right)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
N,Q=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
CL=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    CL[p-1]+=x

AL=[0]*N
ed=[0]*N
def dfs(val, now):
    ed[now]=1
    val+=CL[now]
    AL[now]=val
    for p in L[now]:
        if ed[p]==0:
            dfs(val,p)
dfs(0,0)
print(" ".join(map(str,AL)))

Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
N,Q=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
CL=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    CL[p-1]+=x

AL=[0]*N
ed=[0]*N
q=[(0,0)]
while len(q)!=0:
    now,val=q.pop(-1)
    ed[now] = 1
    val += CL[now]
    AL[now] = val
    for p in L[now]:
        if ed[p] == 0:
            q.append((p,val))
print(" ".join(map(str,AL)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import  Counter
N=int(input())
L=[]
ans=0
for i in range(N):
    s=Counter(list(input()))
    for j,[k,ss] in enumerate(L):
        if s==ss:
            L[j][0]+=1
            ans+=k+1
            break
    else:
        L.append([0,s])
print(ans)

Fixed submission:
from collections import Counter
N=int(input())
L=[''.join(sorted(list(input()))) for i in range(N)]
S=Counter(L)
ans=0
for i in S.values():
    ans+=(i-1)*i//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
L=list(tuple(map(int,input().split())) for _ in range(N))
L.sort(key=lambda x: x[1]*10**6-x[0], reverse=True)
ans=0
for i in range(1,M+1):
    for j,[a,b] in enumerate(L):
        if a<=i:
            ans+=b
            L.pop(j)
            break
print(ans)

Fixed submission:
import sys, heapq
input=sys.stdin.readline
N,M=map(int,input().split())
L=sorted([tuple(map(int,input().split())) for _ in range(N)])
Llen=len(L)
k=0
ans=0
heap=[]
for i in range(1,M+1):
    while k<Llen:
        a,b=L[k]
        if a<=i: heapq.heappush(heap,-b)
        else: break
        k+=1
    if len(heap)>0:
        ans+=-heapq.heappop(heap)
print(ans)
Buggy python submission (verdict: Runtime Error):
print(3*(int(input()**2)))

Fixed submission:
print(3*(int(input())**2))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
input=sys.stdin.readline

N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
n=-1
for x in A:
    if n<x:
        n=x
    elif len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print(len(l)+1)

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

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))

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

N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
for x in A:
    if len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print(len(l))

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

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
for i,x in enumerate(A):
    if len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print(len(l))

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

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))
Buggy python submission (verdict: Time Limit Exceeded):
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
cl=[[0]*w for i in range(h)]
for i in range(h):
    s=0
    for j in range(w):
        if l[i][j]=="#":
            for x in range(s,j):
                cl[i][x]+=j-s
            s=j+1
        elif j==w-1:
            for x in range(s,j+1):
                cl[i][x]+=j-s+1
for i in range(w):
    s=0
    for j in range(h):
        if l[j][i]=="#":
            for x in range(s,j):
                cl[x][i]+=j-s
            s=j+1
        elif j==h-1:
            for x in range(s,j+1):
                cl[x][i]+=j-s+1
print(max([max(x) for x in cl])-1)

Fixed submission:
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
cl=[[0]*w for i in range(h)]
for i in range(h):
    s=0
    for j in range(w):
        if l[i][j]=="#":
            for x in range(s,j):
                cl[i][x]+=j-s
            s=j+1
        elif j==w-1:
            for x in range(s,j+1):
                cl[i][x]+=j-s+1
for i in range(w):
    s=0
    for j in range(h):
        if l[j][i]=="#":
            for x in range(s,j):
                cl[x][i]+=j-s
            s=j+1
        elif j==h-1:
            for x in range(s,j+1):
                cl[x][i]+=j-s+1
print(max([max(x) for x in cl])-1)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=sorted(map(int,input().split()))
b=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])[::-1]
i=0
for num,v in b:
	for j in range(num):
		if a[i]<v and i<n:
			a[i]=v
			i+=1
		else:
			print(sum(a))
			exit()
else:
	print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted(map(int,input().split()))
b=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])[::-1]
i=0
for num,v in b:
	for j in range(num):
		if i<n and a[i]<v:
			a[i]=v
			i+=1
		else:
			print(sum(a))
			exit()
else:
	print(sum(a))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])[::-1]
i=0
for num,v in b:
	for j in range(num):
		if a[i]<v and i<n:
			a[i]=v
			i+=1
		else:
			print(sum(a))
			exit()
else:
	print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=sorted(map(int,input().split()))
b=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])[::-1]
i=0
for num,v in b:
	for j in range(num):
		if i<n and a[i]<v:
			a[i]=v
			i+=1
		else:
			print(sum(a))
			exit()
else:
	print(sum(a))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10100)
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])
				

Fixed submission:
import sys
sys.setrecursionlimit(100100)
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])

Buggy python submission (verdict: Runtime Error):
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])
				

Fixed submission:
import sys
sys.setrecursionlimit(100100)
n=int(input())
route=[[] for i in range(n)]
for i in range(n-1):
	u,v,w=map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
ans=[-1]*n
def dfs(p,d):
	ans[p]=d
	for i,j in route[p]:
		if ans[i]<0:dfs(i,(d+j)%2)
dfs(0,0)
for i in range(n):
	print(ans[i])
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
b=s.count("#")
w=s.count(".")
cnt=0
ind=n-s[::-1].index(".")
p=s[:ind].count("#")
print(min(b,w,p))


Fixed submission:
n=int(input())
s=input()
b=s.count("#")
w=s.count(".")
M=n
noww=0
for i in range(n-1):
    if s[i]==".":
        noww+=1
        if s[i+1]=="#":
            M=min(M,(i-noww+1)+w-noww)

print(min(b,w,M))
Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k=map(int,input().split())
a,b,c=[list(map(int,input().split())) for i in range(3)]
l=[i+j for i in a for j in b]
l.sort(reverse=True)
maxl=[i+j for i in l[:k] for j in c]
maxl.sort(reverse=True)
for a in maxl[:k]:
    print(a)

Fixed submission:
x,y,z,k=map(int,input().split())
a,b,c=[sorted(list(map(int,input().split())),reverse=True) for i in range(3)]
L=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>k:
            break
        for m in range(z):
            if (i+1)*(j+1)*(m+1)>k:
                break
            else:
                L.append(a[i]+b[j]+c[m])
for i in sorted(L,reverse=True)[:k]:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k=map(int,input().split())
a,b,c=[list(map(int,input().split())) for i in range(3)]
l=sorted([i+j for i in a for j in b])[:-k-1:-1]
maxl=sorted([i+j for i in l for j in c])[:-k-1:-1]
for a in maxl:
    print(a)


Fixed submission:
x,y,z,k=map(int,input().split())
a,b,c=[sorted(list(map(int,input().split())),reverse=True) for i in range(3)]
L=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>k:
            break
        for m in range(z):
            if (i+1)*(j+1)*(m+1)>k:
                break
            else:
                L.append(a[i]+b[j]+c[m])
for i in sorted(L,reverse=True)[:k]:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k=map(int,input().split())
a,b,c=[list(map(int,input().split())) for i in range(3)]
l=[i+j for i in a for j in b]
l=sorted(l,reverse=True)[:k]
maxl=sorted([i+j for i in l for j in c])[::-1]
for i in range(k):
    print(maxl[i])


Fixed submission:
x,y,z,k=map(int,input().split())
a,b,c=[sorted(list(map(int,input().split())),reverse=True) for i in range(3)]
L=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>k:
            break
        for m in range(z):
            if (i+1)*(j+1)*(m+1)>k:
                break
            else:
                L.append(a[i]+b[j]+c[m])
for i in sorted(L,reverse=True)[:k]:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
x=[1]*n
for _ in range(q):
    c,d=input().split()
    for i,char in enumerate(s):
        if char == c:
            if d=="L":
                if i==0:
                    x[i]=0
                else:
                    x[i-1]+=x[i]
                    x[i]=0
            else:
                if i==n-1:
                    x[n-1]=0
                else:
                    x[i+1]+=x[i]
                    x[i]=0
print(sum(x))


Fixed submission:
n, q = map(int, input().split())
s = input()
l = 0
r = n - 1
Q = [(input().split()) for i in range(q)]
Q.reverse()
for t,d in Q:
    if s[l] == t and d == "L":
        l += 1
    elif l > 0 and s[l - 1] == t and d == "R":
        l -= 1
    if s[r] == t and d == "R":
        r -= 1
    elif r < n - 1 and s[r + 1] == t and d == "L":
        r += 1
    if l > r:
        break
print(r - l + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a="AC"
s=input()
for _ in range(m):
    x,y=map(int,input().split())
    print(s[x-1:y].count(a))

Fixed submission:
n,m=map(int,input().split())
a="AC"
arr=[0]*(n+1)
s=input()
for i in range(1,n+1):
    arr[i]=arr[i-1]+s[i-1:i+1].count(a)
for _ in range(m):
    x,y=map(int,input().split())
    print(arr[y-1]-arr[x-1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
x=list(map(int,input().split()))
l=[]
while len(x):
    for i,a in enumerate(x):
        if a==i+1:
            index=i
    l.append(x.pop(index))
for i in reversed(l):
    print(i)

Fixed submission:
n=int(input())
x=list(map(int,input().split()))
l=[]
while len(x):
    index=-1
    for i,a in enumerate(x):
        if a==i+1:
            index=i
    if index == -1:
        print(-1)
        break
    l.append(x.pop(index))
else:
    for i in reversed(l):
        print(i)
Buggy python submission (verdict: Time Limit Exceeded):
a,b=map(int,input().split())
x=a
for i in range(a+1,b+1):
    x^=i
print(x)

Fixed submission:
a,b=map(int,input().split())
xa=0
if a==b:
    print(a)
elif b-a<4:
    x=0
    for i in range(a,b+1):
        x^=i
    print(x)
else:
    if a%4:
        for i in range(4-a%4):
            xa^=a+i
    xb=0
    if b%4 != 3:
        for i in reversed(range(b%4+1)):
            xb^=b-i
    print(xa^xb)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
count=0
while True:
    flag=0
    f=s[0]
    for i in range(len(s)):
        if f == '-':
            f=s[i]
        elif f != s[i]:
            count += 2
            s=s[:i-1]+"--"+s[i+1:]
            flag=1
            f='-'
    s=s.replace("-","")
    if len(s)==0 or flag ==0:
        break
print(count)


Fixed submission:
s=input()

print(min(s.count("0"),s.count("1"))*2)
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.count = [1] * (n + 1)

    # find
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # union
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.count[y] += self.count[x]
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                self.count[x] += self.count[y]

    # size
    def size(self, x):
        return self.count[self.par[x]]

    # same
    def issame(self, x, y):
        return self.find(x) == self.find(y)

n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
b = [(j,i)for j in range(1,n+1) for i in range(j+1,n+1)]
U=UnionFind(n)
dis=[0]
cn=0
for i,j in reversed(a):
    if U.issame(i,j)==True:
        dis.append(cn)
    else:
        cn+=U.size(i)*U.size(j)
        dis.append(cn)
    U.union(i, j)
M=int(n*(n-1)/2)
for x in reversed(dis[:-1]):
    print(M-x)

Fixed submission:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.count = [1] * (n + 1)

    # find
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # union
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.count[y] += self.count[x]
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                self.count[x] += self.count[y]

    # size
    def size(self, x):
        return self.count[self.par[x]]

    # same
    def issame(self, x, y):
        return self.find(x) == self.find(y)

n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
U=UnionFind(n)
dis=[0]
cn=0
for i,j in reversed(a):
    if U.issame(i,j)==True:
        dis.append(cn)
    else:
        cn+=U.size(i)*U.size(j)
        dis.append(cn)
    U.union(i, j)
M=int(n*(n-1)/2)
for x in reversed(dis[:-1]):
    print(M-x)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=list(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H):
        if i==0:continue
        m=inf
        M=max(0,i-K)
        for ht,dpt in zip(H[M:i],dp[M:i]):
            m=min(m, dpt+abs(h-ht))
        dp[i]=m
    print(dp[N-1])
    return
if __name__=="__main__":
    main()

Fixed submission:
import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H[1:]):
        m=inf
        for j in range(max(0,i-K+1), i+1):
            m=min(m, dp[j]+abs(h-H[j]))
        dp[i+1]=m
    print(dp[N-1])

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H):
        if i==0:continue
        m=inf
        M=max(0,i-K)
        for ht,dpt in zip(H[M:i],dp[M:i]):
            m=min(m, dpt+abs(h-ht))
        dp[i]=m
    print(dp[N-1])

if __name__=="__main__":
    main()

Fixed submission:
import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H[1:]):
        m=inf
        for j in range(max(0,i-K+1), i+1):
            m=min(m, dp[j]+abs(h-H[j]))
        dp[i+1]=m
    print(dp[N-1])

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H[1:]):
        m=inf
        for j in range(max(0,i-K+1), i+1):
            m=min(m, dp[j]+abs(h-H[j]))
        dp[i+1]=m
    print(dp[N-1])

if __name__=="__main__":
    main()

Fixed submission:
import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

    for i,h in enumerate(H[1:]):
        m=inf
        for j in range(max(0,i-K+1), i+1):
            m=min(m, dp[j]+abs(h-H[j]))
        dp[i+1]=m
    print(dp[N-1])

if __name__=="__main__":
    main()