Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import *

def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t, c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist * _len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					return None
	return d

n, m, s, t, *L = map(int, open(0).read().split())
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for u, v, a, b in zip(*[iter(L)] * 4):
	u -= 1
	v -= 1
	yen[u].append((v, a))
	yen[v].append((u, a))
	snuuk[u].append((v, b))
	snuuk[v].append((u, b))
stoi = SPFA(yen, s - 1)
ttoi = SPFA(snuuk, t - 1)
rest = [10 ** 15 - x - y for x, y in zip(stoi, ttoi)]
ans = list(accumulate(rest[::-1], max))[::-1]
print(*ans)


Fixed submission:
from heapq import *
from itertools import *


def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D


n, m, s, t, *L = map(int, open(0).read().split())
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for u, v, a, b in zip(*[iter(L)] * 4):
	u -= 1
	v -= 1
	yen[u].append((v, a))
	yen[v].append((u, a))
	snuuk[u].append((v, b))
	snuuk[v].append((u, b))
stoi = Dijkstra(yen, s - 1)
ttoi = Dijkstra(snuuk, t - 1)
rest = [10 ** 15 - x - y for x, y in zip(stoi, ttoi)]
ans = list(accumulate(rest[::-1], max))[::-1]
print(*ans)
Buggy python submission (verdict: Runtime Error):
n,*l=map(int,open(0).read().split())
a=sum(l[i]-i-1for i in range(n))//n
f=lambda x:sum(abs(l[i]-i-1-x)for i in range(n))
print(min(f(a-1),f(a),f(a+1)))

Fixed submission:
n=int(input());print(n*(n%2+1))
Buggy python submission (verdict: Runtime Error):
n,*l=map(int,open(0).read().split())
a=sorted([l[i]-i-1for i in range(n)])
f=lambda x:sum(abs(l[i]-i-1-x)for i in range(n))
print(min(f(a[n//2]),f(a[n//2+1])))

Fixed submission:
n,*l=map(int,open(0).read().split())
a=sorted([l[i]-i-1for i in range(n)])
f=lambda x:sum(abs(l[i]-i-1-x)for i in range(n))
print(min(f(a[n//2]),f(a[n//2+(n>1)])))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*;input();a=0
r=[0]+list(accumulate(map(int,input().split())))
for i in set(r):c=r.count(i);a+=c*~-c//2
print(a)

Fixed submission:
from itertools import*
from collections import*
input();a=0
r=[0]+list(accumulate(map(int,input().split())))
for j in Counter(r).values():a+=j*~-j//2
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*;input();a=0
r=[0]+list(accumulate(map(int,input().split())))
for i in set(r):c=r.count(i);a+=c*~-c//2
print(a)

Fixed submission:
from itertools import*
from collections import*
input();a=0
r=[0]+list(accumulate(map(int,input().split())))
for j in Counter(r).values():a+=j*~-j//2
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum(n*all(o[i][(a+j)%n]==o[j][(a+i)%n]for i in r for j in r)for a in r))

Fixed submission:
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

Buggy python submission (verdict: Time Limit Exceeded):
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((1-any(o[(i+b)%n][(a+j)%n]!=o[(j+b)%n][(a+i)%n]for i in r for j in r[i:]))*(n-a-b) for a,b in zip(r+[0]*n,[0]*~-n+r)))

Fixed submission:
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

Buggy python submission (verdict: Time Limit Exceeded):
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

Fixed submission:
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

Buggy python submission (verdict: Time Limit Exceeded):
def s():
	n,*o=open(0)
	n=int(n)
	r=list(range(n))
	print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r)for a,b in zip(r+[0]*n,[0]*~-n+r)))
s()

Fixed submission:
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

Buggy python submission (verdict: Time Limit Exceeded):
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r)for a,b in zip(r+[0]*n,[0]*~-n+r)))

Fixed submission:
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))

Buggy python submission (verdict: Time Limit Exceeded):
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r)for a,b in zip(r+[0]*n,[0]*~-n+r)))

Fixed submission:
n,*o=open(0)
n=int(n)
r=list(range(n))
print(sum((n-a-b)*all(o[(i+b)%n][(a+j)%n]==o[(j+b)%n][(a+i)%n]for i in r for j in r[i:])for a,b in zip(r+[0]*n,[0]*~-n+r)))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*
n,c,*L=map(int,open(0).read().split())
acc=[a-x for x,a in zip(L[::2],accumulate(L[1::2]))]
R=L[::-1]
rev=[a-(c-x) for x,a in zip(R[1::2],accumulate(R[::2]))]
p=max(max([0]+rev[:n-i-1])+a-b for i,(a,b) in enumerate(zip(acc,L[::2])))
q=max(max([0]+acc[:n-i-1])+a-(c-b) for i,(a,b) in enumerate(zip(rev,R[1::2])))
r=max(0,max(acc),max(rev))
print(max(p,q,r))

Fixed submission:
from itertools import*
n,c,*L=map(int,open(0).read().split())
acc=[a-x for x,a in zip(L[::2],accumulate(L[1::2]))]
acc_max=list(accumulate([0]+acc,max))
R=L[::-1]
rev=[a-(c-x) for x,a in zip(R[1::2],accumulate(R[::2]))]
rev_max=list(accumulate([0]+rev,max))
p=max(rev_max[n-i-1]+a-b for i,(a,b) in enumerate(zip(acc,L[::2])))
q=max(acc_max[n-i-1]+a-(c-b) for i,(a,b) in enumerate(zip(rev,R[1::2])))
r=max(0,acc_max[-1],rev_max[-1])
print(max(p,q,r))

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*
n,c,*L=map(int,open(0).read().split())
acc=[a-x for x,a in zip(L[::2],accumulate(L[1::2]))]
R=L[::-1]
rev=[a-(c-x) for x,a in zip(R[1::2],accumulate(R[::2]))]
p=max(max([0]+rev[:n-i-1])+a-b for i,(a,b) in enumerate(zip(acc,L[::2])))
q=max(max([0]+acc[:n-i-1])+a-(c-b) for i,(a,b) in enumerate(zip(rev,R[1::2])))
r=max(0,max(acc),max(rev))
print(max(p,q,r))

Fixed submission:
from itertools import*
n,c,*L=map(int,open(0).read().split())
acc=[a-x for x,a in zip(L[::2],accumulate(L[1::2]))]
acc_max=list(accumulate([0]+acc,max))
R=L[::-1]
rev=[a-(c-x) for x,a in zip(R[1::2],accumulate(R[::2]))]
rev_max=list(accumulate([0]+rev,max))
p=max(rev_max[n-i-1]+a-b for i,(a,b) in enumerate(zip(acc,L[::2])))
q=max(acc_max[n-i-1]+a-(c-b) for i,(a,b) in enumerate(zip(rev,R[1::2])))
r=max(0,acc_max[-1],rev_max[-1])
print(max(p,q,r))
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())
l=[]
for i in range(a,b+1):
	if min(i-a,b-i)<k:
		l.append(i)
print(*l,sep='\n')

Fixed submission:
a,b,k=map(int,input().split())
aa=set(range(a,min(b+1,a+k)))
bb=set(range(max(b-k+1,a),b+1))
print(*sorted(aa|bb),sep='\n')
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split());print(sum(n//b*(b-k)+max(n%b-k+(k>0),0)for b in range(k,n+1)))

Fixed submission:
n,k=map(int,input().split());print(sum(n//b*(b-k)+max(n%b-k+(k>0),0)for b in range(k+1,n+1)))
Buggy python submission (verdict: Runtime Error):
h,w,d,*l=map(int,open(0).read().split())
s=h*w+1;x=[0]*s;y=[0]*s;k=[0]*s
for i,a in enumerate(l[:s]):x[a]=i//w;y[a]=i%w
for i in range(d+1,s-1):k[i]=k[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for l,r in zip(l[s::2],l[s+1::2]):print(k[r]-k[l])

Fixed submission:
h,w,d,*l=map(int,open(0).read().split())
s=h*w
x=[0]*(s+1)
y=[0]*(s+1)
for i,a in enumerate(l[:s]):
	x[a]=i//w
	y[a]=i%w
ref=[0]*(s+1)
for i in range(d+1,s+1):
	ref[i]=ref[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for l,r in zip(l[s+1::2],l[s+2::2]):
	print(ref[r]-ref[l])
Buggy python submission (verdict: Runtime Error):
from scipy.spatial import ConvexHull as CH
import numpy as np
norm=np.linalg.norm
n,*t=map(int,open(0).read().split())
a=np.reshape(t,(n,2))
h=CH(a).vertices
l=len(h)
for i in range(n):
	if i in h:
		j=np.where(h==i)[0]
		f,s,t=a[h[j-1]],a[i],a[h[(j+1)%l]]
		print(np.arccos(np.inner(t-s,s-f)/(norm(t-s)*norm(s-f)))[0,0]/(2*np.pi))
	else:
		print(0.)

Fixed submission:
from scipy.spatial import ConvexHull as CH
import numpy as np
norm=np.linalg.norm
n,*t=map(int,open(0).read().split())
a=np.reshape(t,(n,2))
try:
	h = CH(a).vertices
except:
	a=a-10**6
	if np.all(a[:,0]==a[0,0]):
		a=np.fliplr(a)
	b=a[:,0]
	M=np.argmax(b)
	m=np.argmin(b)
	for i in range(n):
		print(0.5*(i in (m,M)))
	exit()
l=len(h)
for i in range(n):
	if i in h:
		j=np.where(h==i)[0]
		f,s,t=a[h[j-1]],a[i],a[h[(j+1)%l]]
		print(np.arccos(np.inner(t-s,s-f)/(norm(t-s)*norm(s-f)))[0,0]/(2*np.pi))
	else:
		print(0.)
Buggy python submission (verdict: Runtime Error):
a=int(input().replace(" ",""))
print("YNeos"[(a**0.5)*2!=floor(a)::2])

Fixed submission:
a=int(input().replace(" ",""))
print("No"if a**0.5%1 else "Yes")
Buggy python submission (verdict: Time Limit Exceeded):
w=input()
a=[(i+1)*(j=="0") for i,j in enumerate(w)]
b=[(i+1)*(j=="1") for i,j in enumerate(w)]
l=len(w)
w=list(w)
for t in range(1,l+1):
	m=min(max(a[:t]),max(b[:t]))
	if l-m<t:
		print(t-1)
		exit()
print(l)

Fixed submission:
w=input()
a=[(i+1)*(j=="0") for i,j in enumerate(w)]
b=[(i+1)*(j=="1") for i,j in enumerate(w)]
l=len(w)
ma=a[0];mb=b[0]
for t in range(1,l+1):
	ma=max(ma,a[t-1])
	mb=max(mb,b[t-1])
	m=min(ma,mb)
	if l-m<t:
		print(t-1)
		exit()
print(l)
Buggy python submission (verdict: Time Limit Exceeded):
_,*l=map(int,open(0).read().split())
a=0
for i in list(set(l)):
	c=l.count(i)
	a+=c-i*(c>=i)
print(a)

Fixed submission:
from collections import*
_,*l=map(int,open(0).read().split())
a=0
c=Counter(l)
for i in list(set(l)):
	j=c[i]
	a+=j-i*(i<=j)
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
_,*l=map(int,open(0).read().split())
a=0
for i in list(set(l)):
	c=l.count(i)
	a+=c-i*(c>=i)
print(a)

Fixed submission:
from collections import*
_,*l=map(int,open(0).read().split())
a=0
c=Counter(l)
for i in list(set(l)):
	j=c[i]
	a+=j-i*(i<=j)
print(a)
Buggy python submission (verdict: Runtime Error):
f,*l=map(len,input().split("T"))
x,y=map(int,input().split())
z=8000;bx=1<<f+z;by=1<<z
for dy,dx in zip(*[iter(l)]*2):bx=bx<<dx|bx>>dx;by=by<<dy|by>>dy
print("Yes"*(bx&(1<<x+z) and by&(1<<y+z))or"No")

Fixed submission:
l = [len(c) for c in input().split("T")]
x, y = map(int, input().split())
bx = 1 << l.pop(0) + 8000
by = 1 << 8000
for i, d in enumerate(l):
	if i % 2:
		bx = (bx << d) | (bx >> d)
	else:
		by = (by << d) | (by >> d)
print("Yes" if bx & (1 << x + 8000) and by & (1 << y + 8000) else "No")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import*;n,k,*a=map(int,open(0).read().split());print(n-sum(Counter(a).most_common()[i][1] for i in range(min(len(set(a)),k))))

Fixed submission:
from collections import Counter
n,k,*a=map(int,open(0).read().split())
if len(set(a))<=k:
	print(0)
	exit()
else:
	c=Counter(a).most_common(k)
	n-=sum(c[i][1] for i in range(k))
	print(n)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=1
while a<k and n:a*=2;n-=1
print(a+k*n)

Fixed submission:
n,k=map(int,open(0))
a=1
while a<k and n:a*=2;n-=1
print(a+k*n)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	n = int(input())
	*t, = map(int, input().split())
	tot = sum(t)
	*v, = map(int, input().split())
	lim1 = []
	lim2 = [(1, 0, 0), (-1, tot, tot)]
	til = 0
	for t1, t2, v1 in zip([0] + t, t, v):
		lim1.append((til, til + t2, v1))
		lim2.append((-1, til, til + v1))
		lim2.append((1, til + t2, v1 - (til + t2)))
		til += t2

	def mi(time):
		ret = float("inf")
		for l, r, lim in lim1:
			if l <= time <= r:
				ret = min(ret, lim)
		for f, tt, y in lim2:
			if f == -1 and time <= tt:
				ret = min(ret, y - time)
			if f == 1 and time >= tt:
				ret = min(ret, time + y)
		return ret

	print(sum(mi(i / 2) for i in range(tot * 2 + 1)) / 2)

if __name__ == '__main__':
	main()

Fixed submission:
def main():
	n = int(input())
	*t, = map(int, input().split())
	tot = sum(t)
	*v, = map(int, input().split())
	lim1 = []
	lim2 = [(1, 0, 0), (-1, tot, tot)]
	til = 0
	for t1, t2, v1 in zip([0] + t, t, v):
		lim1.append((til, til + t2, v1))
		lim2.append((-1, til, til + v1))
		lim2.append((1, til + t2, v1 - (til + t2)))
		til += t2

	def mi(time):
		ret = float("inf")
		for l, r, lim in lim1:
			if l <= time <= r:
				ret = min(ret, lim)
		for f, tt, y in lim2:
			if f == -1 and time <= tt:
				ret = min(ret, y - time)
			if f == 1 and time >= tt:
				ret = min(ret, time + y)
		return ret

	print(sum(mi(i / 2) for i in range(tot * 2 + 1)) / 2)

if __name__ == '__main__':
	main()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
*t,=map(int,input().split())
tot=sum(t)
*v,=map(int,input().split())
lim1=[]
lim2=[(1,0,0),(-1,tot,tot)]
til=0
for t1,t2,v1 in zip([0]+t,t,v):
	lim1.append((til,til+t2,v1))
	lim2.append((-1,til,til+v1))
	lim2.append((1,til+t2,v1-(til+t2)))
	til+=t2
def mi(time):
	ret=float("inf")
	for l,r,lim in lim1:
		if l<=time<=r:
			ret=min(ret,lim)
	for f,tt,y in lim2:
		if f==-1 and time<=tt:
			ret=min(ret,y-time)
		if f==1 and time>=tt:
			ret=min(ret,time+y)
	return ret
print(sum(mi(i/2) for i in range(tot*2+1))/2)

Fixed submission:
def main():
	n = int(input())
	*t, = map(int, input().split())
	tot = sum(t)
	*v, = map(int, input().split())
	lim1 = []
	lim2 = [(1, 0, 0), (-1, tot, tot)]
	til = 0
	for t1, t2, v1 in zip([0] + t, t, v):
		lim1.append((til, til + t2, v1))
		lim2.append((-1, til, til + v1))
		lim2.append((1, til + t2, v1 - (til + t2)))
		til += t2

	def mi(time):
		ret = float("inf")
		for l, r, lim in lim1:
			if l <= time <= r:
				ret = min(ret, lim)
		for f, tt, y in lim2:
			if f == -1 and time <= tt:
				ret = min(ret, y - time)
			if f == 1 and time >= tt:
				ret = min(ret, time + y)
		return ret

	print(sum(mi(i / 2) for i in range(tot * 2 + 1)) / 2)

if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)+[0]
Y=sorted(y for x,y in p)
ans=float("inf")
for i,mx in enumerate(X[:-k]):
	for Mx in X[i+k-1:-1]:
		for my,My in combinations(Y,2):
			if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
				ans=min(ans,(Mx-mx)*(My-my))
print(ans)

Fixed submission:
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)
Y=sorted(y for x,y in p)
ans=float("inf")
for mx,Mx in combinations(X,2):
	for my,My in combinations(Y,2):
		if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
			ans=min(ans,(Mx-mx)*(My-my))
print(ans)


Fixed submission:
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)
Y=sorted(y for x,y in p)
ans=float("inf")
for mx,Mx in combinations(X,2):
	for my,My in combinations(Y,2):
		if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
			ans=min(ans,(Mx-mx)*(My-my))
print(ans)

Fixed submission:
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import*

n,m,o=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
d=[[INF]*n for _ in range(n)]
r=range
for i in r(n):
	d[i][i]=0
for _ in r(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=d[b-1][a-1]=c
for k in r(n):
	for i in r(n):
		for j in r(n):
			d[i][j]=min(d[i][j],d[i][k]+d[k][j])
v=[[d[i-1][j-1]for j in R]for i in R]
m=INF
for t in permutations(r(o)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		m=min(m,a)
print(m)

Fixed submission:
from itertools import permutations

n,m,r=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
dist=[[INF]*n for _ in range(n)]
for i in range(n):
	dist[i][i]=0
for _ in range(m):
	a,b,c=map(int,input().split())
	dist[a-1][b-1]=c
	dist[b-1][a-1]=c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
v=[]
for i in R:
	t=[]
	for j in R:
		t.append(dist[i-1][j-1])
	v.append(t)
mn=INF
for t in permutations(range(r)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		mn=min(mn,a)
print(mn)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist=[[None]*n for _ in range(n)]
dist_f_k=[0]*n

for _ in range(n-1):
	a,b,c=map(int,input().split())
	con[a-1].append(b-1)
	con[b-1].append(a-1)
	dist[a-1][b-1]=dist[b-1][a-1]=c

q,k=map(int,input().split())
dist_f_k[k-1]=None
que=deque([(k-1,0)])
while que:
	cur,d=que.popleft()
	for nxt in con[cur]:
		if dist_f_k[nxt]==0:
			tmp=d+dist[cur][nxt]
			que.append((nxt,tmp))
			dist_f_k[nxt]=tmp

for _ in range(q):
	x,y=map(int,input().split())
	print(dist_f_k[x-1]+dist_f_k[y-1])

Fixed submission:
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist_f_k=[0]*n

for _ in range(n-1):
	a,b,c=map(int,input().split())
	con[a-1].append((b-1,c))
	con[b-1].append((a-1,c))

q,k=map(int,input().split())
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

for _ in range(q):
	x,y=map(int,input().split())
	print(dist_f_k[x-1]+dist_f_k[y-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist=[[None]*n for _ in range(n)]
dist_f_k=[0]*n

for _ in range(n-1):
	a,b,c=map(int,input().split())
	con[a-1].append(b-1)
	con[b-1].append(a-1)
	dist[a-1][b-1]=dist[b-1][a-1]=c

q,k=map(int,input().split())
dist_f_k[k-1]=None
que=deque([(k-1,0)])
while que:
	cur,d=que.popleft()
	for nxt in con[cur]:
		if dist_f_k[nxt]==0:
			tmp=d+dist[cur][nxt]
			que.append((nxt,tmp))
			dist_f_k[nxt]=tmp

for _ in range(q):
	x,y=map(int,input().split())
	print(dist_f_k[x-1]+dist_f_k[y-1])

Fixed submission:
from collections import deque
n=int(input())
con=[[] for _ in range(n)]
dist_f_k=[0]*n

for _ in range(n-1):
	a,b,c=map(int,input().split())
	con[a-1].append((b-1,c))
	con[b-1].append((a-1,c))

q,k=map(int,input().split())
que=deque([k-1])
while que:
	cur=que.popleft()
	for nxt,dd in con[cur]:
		if dist_f_k[nxt]==0 and nxt!=k-1:
			que.append(nxt)
			dist_f_k[nxt]=dist_f_k[cur]+dd

for _ in range(q):
	x,y=map(int,input().split())
	print(dist_f_k[x-1]+dist_f_k[y-1])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
prnt((n-1)*(m-1))

Fixed submission:
n,m=map(int,input().split());print(~-m*~-n)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = [0] * (m + 1)
cur = [0] * n
done = [0] * (m + 1)
for i in range(n):
	cnt[a[i][0]] += 1
	cur[i] = a[i][0]
ans = max(cnt)
for _ in range(m - 1):
	col = cnt.index(max(cnt))
	done[col] = 1
	for i in range(n):
		if cur[i] == col:
			j = 0
			while done[a[i][j]]:
				j += 1
			t = a[i][j]
			cur[i] = t
			cnt[t] += 1
	cnt[col] = 0
	ans = min(ans, max(cnt))
print(ans)


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

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = [0] * (m + 1)
cur = [0] * n
done = [0] * (m + 1)
for i in range(n):
	cnt[a[i][0]] += 1
	cur[i] = a[i][0]
ans = max(cnt)
for _ in range(m - 1):
	col = cnt.index(max(cnt))
	done[col] = 1
	for i in range(n):
		if cur[i] == col:
			j = 0
			while done[a[i][j]]:
				j += 1
			t = a[i][j]
			cur[i] = t
			cnt[t] += 1
	cnt[col] = 0
	ans = min(ans, max(cnt))
print(ans)
Buggy python submission (verdict: Runtime Error):
n,*a=map(int,open(0).read().split())
x=a[0]
y=a[1:]
ans=abs(x-y)
for i in a[1:-1]:
  x+=i
  y-=i
  ans=min(ans,abs(x-y))
print(ans)

Fixed submission:
n,*a=map(int,open(0).read().split())
x=a[0]
y=sum(a[1:])
ans=abs(x-y)
for i in a[1:-1]:
  x+=i
  y-=i
  ans=min(ans,abs(x-y))
print(ans)
Buggy python submission (verdict: Runtime Error):
x,a,b=map(int,input().split());print(("delicious,"safe","dangerous")[(b-a>0)+(b-a>x)])

Fixed submission:
x,a,b=map(int,input().split());print(("delicious","safe","dangerous")[(b-a>0)+(b-a>x)])
Buggy python submission (verdict: Runtime Error):
N,W,*l = map(int,open(0).read().split())
wl = l[::2]
vl = l[1::2]
M = N*max(vl)
INF = float("inf")
dp = [[INF]*(M+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
	w,v = wl[i],vl[i]
	for j in range(M+1):
		if j >= v:
			dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
		else:
			dp[i+1][j] = dp[i][j]

ans=0
for val,wei in enumerate(dp[-1]):
	if wei <= W:
		ans = max(ans,val)
print(ans)


Fixed submission:
N,W,*L=map(int,open(0).read().split())
w1=L[0]
l=[[] for _ in range(4)]
for w,v in zip(*[iter(L)]*2):
	l[w-w1].append(v)
l=[sorted(t)[::-1] for t in l]
a,b,c,d=map(len,l)
ans=0
for h in range(a+1):
	for i in range(b+1):
		for j in range(c+1):
			for k in range(d+1):
				if w1*h+(w1+1)*i+(w1+2)*j+(w1+3)*k<=W:
					ans=max(ans,sum(l[0][:h]+l[1][:i]+l[2][:j]+l[3][:k]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
if all(n%i for i in range(2,int(n**.5)+1)):
	print(len(str(n)))
	exit()
for i in range(int(0-n**.5//-1),n+1):
	if n%i==0:
		print(len(str(i)))
		exit()

Fixed submission:
n=int(input())
for i in range(int(0-n**.5//-1),1,-1):
	if n%i==0:
		print(len(str(n//i)))
		exit()
print(len(str(n)))
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
print(min(s,c//2)+max(0,c-s*2)//4)

Fixed submission:
s,c=map(int,input().split())
print(min(s,c//2)+max(0,c-s*2)//4)
Buggy python submission (verdict: Time Limit Exceeded):
n,ma,mb,*L=map(int,open(0).read().split())
INF=float('inf')
dp=[[INF]*420 for _ in range(420)]
dp[0][0]=0
for a,b,c in zip(*[iter(L)]*3):
	for i in range(400,-1,-1):
		for j in range(400,-1,-1):
			t=dp[i][j]+c
			if dp[i+a][j+b]>t:
				dp[i+a][j+b]=t
ans=INF
_ma,_mb=ma,mb
while _ma<410>_mb:
	ans=min(ans,dp[_ma][_mb])
	_ma+=ma
	_mb+=mb
print(ans if ans<INF else -1)

Fixed submission:
n,ma,mb,*L=map(int,open(0).read().split())
INF=float('inf')
dp=[[INF]*420 for _ in range(420)]
dp[0][0]=0
for a,b,c in zip(*[iter(L)]*3):
	for i in range(400,-1,-1):
		for j in range(400,-1,-1):
			t=dp[i][j]+c
			if dp[i+a][j+b]>t:
				dp[i+a][j+b]=t
ans=INF
_ma,_mb=ma,mb
while _ma<410>_mb:
	ans=min(ans,dp[_ma][_mb])
	_ma+=ma
	_mb+=mb
print(ans if ans<INF else -1)