Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
p=s[0]
cnt=1
q=[]
for i in range(len(s)-1):
	if s[i+1]==p:
		cnt+=1
	else:
		q.append(cnt)
		cnt=1
		p=s[i+1]
q.append(cnt)
if q[-1]%2==0:
	cnt=True
else:
	cnt=False
ans=0
if cnt==True:
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)
	exit()
if len(q)==1:
	print(len(s)*k//2)
	exit()
for i in range(len(q)-1):
	ans+=q[i+1]//2
ans*=k
ans+=q[0]//2
if s[0]==s[-1]:
	ans+=(q[0]+q[-1])//2*(k-1)
	ans+=q[-1]//2
	print(ans)
	print(2/0)
else:
	ans=0
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)

Fixed submission:
s=input()
k=int(input())
p=s[0]
cnt=1
q=[]
for i in range(len(s)-1):
	if s[i+1]==p:
		cnt+=1
	else:
		q.append(cnt)
		cnt=1
		p=s[i+1]
q.append(cnt)
if q[-1]%2==0:
	cnt=True
else:
	cnt=False
ans=0
if cnt==True:
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)
	exit()
if len(q)==1:
	print(len(s)*k//2)
	exit()
for i in range(len(q)-2):
	ans+=q[i+1]//2
ans*=k
ans+=q[0]//2
if s[0]==s[-1]:#miss
	ans+=(q[0]+q[-1])//2*(k-1)
	ans+=q[-1]//2
	print(ans)
	exit()
else:
	ans=0
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)

Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
p=s[0]
cnt=1
q=[]
for i in range(len(s)-1):
	if s[i+1]==p:
		cnt+=1
	else:
		q.append(cnt)
		cnt=1
		p=s[i+1]
q.append(cnt)
if q[-1]%2==0:
	cnt=True
else:
	cnt=False
ans=0
if cnt==True:
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)
	exit()
if len(q)==1:
	print(len(s)*k//2)
	exit()
for i in range(k-2):
	ans+=q[i+1]//2
ans*=k
ans+=q[0]//2
ans+=(q[0]+q[1])//2*(k-1)
ans+=q[-1]//2
print(ans)

Fixed submission:
s=input()
k=int(input())
p=s[0]
cnt=1
q=[]
for i in range(len(s)-1):
	if s[i+1]==p:
		cnt+=1
	else:
		q.append(cnt)
		cnt=1
		p=s[i+1]
q.append(cnt)
if q[-1]%2==0:
	cnt=True
else:
	cnt=False
ans=0
if cnt==True:
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)
	exit()
if len(q)==1:
	print(len(s)*k//2)
	exit()
for i in range(len(q)-2):
	ans+=q[i+1]//2
ans*=k
ans+=q[0]//2
if s[0]==s[-1]:#miss
	ans+=(q[0]+q[-1])//2*(k-1)
	ans+=q[-1]//2
	print(ans)
	exit()
else:
	ans=0
	for i in range(len(q)):
		ans+=q[i]//2
	print(ans*k)
Buggy python submission (verdict: Time Limit Exceeded):
inf=10**9
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
dp=[[inf]*(2**n) for _ in range(m+1)]
def two(i):
	return "0"*(n-len(bin(i)[2:]))+bin(i)[2:]
for i in range(m+1):
	dp[i][0]=0
for i in range(m):
	a,b=map(int,input().split())
	r=0
	c=list(map(int,input().split()))
	for p in c:
		r+=2**(p-1)
	for j in range(2**n):
		x=j|r
		dp[i+1][x]=min(dp[i][j]+a,dp[i][x],dp[i+1][x])
	for j in range(2**n):
		dp[i+1][j]=min(dp[i+1][j],dp[i][j])
print(dp[-1][-1]) if dp[-1][-1]!=inf else print(-1)

Fixed submission:
inf=10**9
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
dp=[[inf]*(2**n) for _ in range(m+1)]
def two(i):
	return "0"*(n-len(bin(i)[2:]))+bin(i)[2:]
for i in range(m+1):
	dp[i][0]=0
for i in range(m):
	a,b=map(int,input().split())
	r=0
	c=list(map(int,input().split()))
	for p in c:
		r+=2**(p-1)
	for j in range(2**n):
		x=j|r
		dp[i+1][x]=min(dp[i][j]+a,dp[i][x],dp[i+1][x])
	for j in range(2**n):
		dp[i+1][j]=min(dp[i+1][j],dp[i][j])
print(dp[-1][-1]) if dp[-1][-1]!=inf else print(-1)
Buggy python submission (verdict: Runtime Error):
s=input()
t=input()
a=[]
import bisect
for i in range(len(s)):
	a.append([ord(s[i]),i])
a.sort()
c=[]
d=[]
for i in range(len(s)):
	c.append(a[i][0])
	d.append(a[i][1])
b=[]
e=[]
for i in range(len(t)):
	if c[0]<=ord(t[i])<=c[-1]:
		b.append(bisect.bisect_left(c,ord(t[i])))
	else:
		print(-1)
		exit()
for i in range(len(t)):
	e.append(d[b[i]])
ans=e[0]+1
cnt=0
for i in range(len(e)-1):
	if e[i]<e[i+1]:
		ans+=e[i+1]-e[i]
		cnt=0
	elif e[i]==e[i+1] and s[i]==s[i+1]:
		ans+=1
	else:
		ans+=len(s)-e[i]+e[i+1]
		cnt=0
print(ans)

Fixed submission:
s=input()
t=input()
s*=2
next=[[-1]*26 for _ in range(len(s))]
alph=[[]for _ in range(26)]
for i in range(len(s)):
	alph[ord(s[i])-ord("a")].append(i)
from bisect import bisect_right
for i in range(len(s)//2):
	for j in range(26):
		if len(alph[j])>bisect_right(alph[j],i):
			next[i][j]=alph[j][bisect_right(alph[j],i)]
ans=1
now=len(s)//2-1
for x in t:
	r=ord(x)-ord("a")
	now=next[now][r]
	if now==-1:
		print(-1)
		exit()
	if now>=len(s)//2:
		ans+=len(s)//2
		now-=len(s)//2
print(ans+now-len(s)//2)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=len(s)
a=[]
c=[0]*n
for i in range(n-1):
	if s[i]!=s[i+1]:
		a.append(i)
for i in range(n):
	if s[i]=="L":
		for j in range(n):
			if s[i-j]=="R":
				idou=j
				break
		if idou%2==0:
			c[i-j]+=1
		else:
			c[i-j+1]+=1
	else:
		for j in range(n):
			if s[i+j]=="L":
				idou=j
				break
		if idou%2==0:
			c[i+j]+=1
		else:
			c[i+j-1]+=1
print(*c)



Fixed submission:
import bisect
s=input()
n=len(s)
a=[]
c=[0]*n
for i in range(n-1):
	if s[i]!=s[i+1]:
		a.append(i)


for i in range(n):
	if s[i]=="L":
		pp=bisect.bisect_left(a,i)
		idou=i-a[pp-1]+1
		if idou%2==0:
			c[a[pp-1]+1]+=1
		else:
			c[a[pp-1]]+=1
	else:
		pp=bisect.bisect_left(a,i)
		idou=a[pp]-i
		if idou%2==0:
			c[a[pp]]+=1
			
		else:
			c[a[pp]+1]+=1
			
print(*c)
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
s=input()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
	p=pow(10,i,13)
	if s[i]=="?":	
		for k in range(13):
			for j in range(10):
				dp[i+1][(k+p*j)%13]+=dp[i][k]
				dp[i+1][(k+p*j)%13]%=mod
	else:
		for k in range(13):
			dp[i+1][(k+p*int(s[i]))%13]+=dp[i][k]
			dp[i+1][(k+p*int(s[i]))%13]%=mod
print(dp[-1][5])


Fixed submission:
mod=10**9+7
s=input()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
	p=pow(10,i,13)
	if s[i]=="?":	
		for k in range(13):
			for j in range(10):
				dp[i+1][(k+p*j)%13]+=dp[i][k]
				dp[i+1][(k+p*j)%13]%=mod
	else:
		for k in range(13):
			dp[i+1][(k+p*int(s[i]))%13]+=dp[i][k]
			dp[i+1][(k+p*int(s[i]))%13]%=mod
print(dp[-1][5])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
ma=max(a)
keiken=0
b=[]
for i in range(n):
	if a[i]==ma and keiken==0:
		for ii in range(n):
			if ii!=i:
				b.append(a[ii])
		print(max(b))
	else:
		print(ma)


Fixed submission:
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
b=sorted(a)
for i in range(n):
	if a[i]==b[n-1]:
		print(b[n-2])
	else:
		print(b[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
ma=max(a)
keiken=0
b=[]
for i in range(n):
	if a[i]==ma and keiken==0:
		for ii in range(n):
			if ii!=i:
				b.append(a[ii])
		print(max(b))
	else:
		print(ma)


Fixed submission:
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
b=sorted(a)
for i in range(n):
	if a[i]==b[n-1]:
		print(b[n-2])
	else:
		print(b[n-1])
Buggy python submission (verdict: Runtime Error):
from math import ceil
mod=10**9+7
def comb(a,b):
	if a<b:
		return 0
	fac=[1]
	for i in range(a):
		fac.append(fac[i]*(i+1))
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
n,k=map(int,input().split())
for i in range(1,k+1):
	q=comb(n-k+1,i)
	qq=comb(k-i+i-1,i-1)
	print(q*qq%mod)



Fixed submission:
s=input()
if s[0]==s[1] and s[2]==s[3] and s[1]==s[2]:
 print("No")
elif s[0]==s[1] and s[2]==s[3]:
 print("Yes")
elif s[0]==s[2] and s[1]==s[3]:
 print("Yes")
elif s[0]==s[3] and s[1]==s[2]:
 print("Yes")
else:
 print("No")
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
mod=10**9+7
def comb(a,b):
	if a<b:
		return 0
	fac=[1]
	for i in range(a):
		fac.append(fac[i]*(i+1))
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
n,k=map(int,input().split())
for i in range(1,k+1):
	q=comb(n-k+1,i)
	qq=comb(k-i+i-1,i-1)
	print(q*qq%mod)



Fixed submission:
from math import ceil
mod=10**9+7
fac=[1]
for i in range(2002):
	fac.append(fac[i]*(i+1))
def comb(a,b):
	if a<b:
		return 0
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
n,k=map(int,input().split())
for i in range(1,k+1):
	q=comb(n-k+1,i)
	qq=comb(k-i+i-1,i-1)
	print(q*qq%mod)

Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
mod=10**9+7
def comb(a,b):
	if a<b:
		return 0
	fac=[1]
	for i in range(a):
		fac.append(fac[i]*(i+1))
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
n,k=map(int,input().split())
for i in range(1,k+1):
	q=comb(n-k+1,i)
	qq=comb(k-i+i-1,i-1)
	print(q*qq%mod)



Fixed submission:
from math import ceil
mod=10**9+7
fac=[1]
for i in range(2002):
	fac.append(fac[i]*(i+1))
def comb(a,b):
	if a<b:
		return 0
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
n,k=map(int,input().split())
for i in range(1,k+1):
	q=comb(n-k+1,i)
	qq=comb(k-i+i-1,i-1)
	print(q*qq%mod)
Buggy python submission (verdict: Runtime Error):
n,x=map(int,input().split())
l=list(map(int,input().split()))
k=0
ans=1
while k<=x:
 k+=l[ans-1]
 if k<=x:
  ans+=1
print(ans)

Fixed submission:
n,x=map(int,input().split())
l=list(map(int,input().split()))
d=0
ans=1
while d<=x and ans<=n:
 d+=l[ans-1]
 if d>x:
  break
 else:
  ans+=1
print(min(ans,n+1))
Buggy python submission (verdict: Runtime Error):
w,h,x,y=map(int,input().split())
if x!=0 and x!=w and y!=0 and y!=h:
 a=min(w-x,x)
 b=min(y,h-y)
 ans1=max(a*h,b*w)
 if a*h==b*w:
  ans2=1
 else:
  ans2=0
 print(ans1,ans2)
else:
  break

Fixed submission:
w,h,x,y=map(int,input().split())
ans1=w*h/2
if w/2==x and  h/2==y:
 ans2=1
else:
 ans2=0
print(ans1,ans2)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
total=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(total[i][j]+1)%mod
		total[i+1][j+1]=(total[i+1][j]+total[i][j+1]-total[i][j]+dp[i+1][j+1])%mod
print((total[-1][-1]+1)%mod)

Fixed submission:
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
total=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(total[i][j]+1)%mod
		total[i+1][j+1]=(total[i+1][j]+total[i][j+1]-total[i][j]+dp[i+1][j+1])%mod
print((total[-1][-1]+1)%mod)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a.sort()
minus=sum(a[0:n//2])
plus=sum(a)-minus
print(plus-minus)
if n%2==0:
 s=a[0]
 for i in range(1,n//2):
  print(a[n-i],s)
  s=a[n-i]-s
  print(a[i],s)
  s=a[i]-s
 print(a[n//2],s)
else:
 s=a[n-1]
 for i in range(n//2):
  print(a[i],s)
  s=a[i]-s
  print(a[n-(i+2)],s)
  s=a[n-(i+2)]-s

Fixed submission:
n,k=map(int,input().split())
if k==1:
 print(0)
else:
 print(n-k)
Buggy python submission (verdict: Runtime Error):
n,a,b,c,d=map(int,input().split())
s=input()
for i in range(n-1):
	if s[i]==s[i+1]=="#":
		print("No")
		exit()
three=0
s="#"+s
for i in range(b,d+1):
	if s[i]==s[i+1]==s[i-1]==".":
		three=True
if c<d:
	print("Yes")
elif three==True:
	print("Yes")
else:
	print("No")

Fixed submission:
n,a,b,c,d=map(int,input().split())
s=input()
for i in range(a,d-1):
	if s[i]==s[i+1]=="#":
		print("No")
		exit()
three=0
s="#"+s+"#"
for i in range(b,d+1):
	if s[i]==s[i+1]==s[i-1]==".":
		three=True
if c<d:
	print("Yes")
elif three==True:
	print("Yes")
else:
	print("No")

Buggy python submission (verdict: Runtime Error):
n,a,b,c,d=map(int,input().split())
s=input()
for i in range(n-1):
	if s[i]==s[i+1]=="#":
		print("No")
		exit()
three=0
s="#"+s
for i in range(b,d+1)
	if s[i]==s[i+1]==s[i-1]==".":
		three=True
if c<d:
	print("Yes")
elif three==True:
	print("Yes")
else:
	print("No")

Fixed submission:
n,a,b,c,d=map(int,input().split())
s=input()
for i in range(a,d-1):
	if s[i]==s[i+1]=="#":
		print("No")
		exit()
three=0
s="#"+s+"#"
for i in range(b,d+1):
	if s[i]==s[i+1]==s[i-1]==".":
		three=True
if c<d:
	print("Yes")
elif three==True:
	print("Yes")
else:
	print("No")

Buggy python submission (verdict: Runtime Error):
print("Yes)

Fixed submission:
n,a,b,c,d=map(int,input().split())
s=input()
for i in range(a,d-1):
	if s[i]==s[i+1]=="#":
		print("No")
		exit()
three=0
s="#"+s+"#"
for i in range(b,d+1):
	if s[i]==s[i+1]==s[i-1]==".":
		three=True
if c<d:
	print("Yes")
elif three==True:
	print("Yes")
else:
	print("No")
Buggy python submission (verdict: Runtime Error):
n=int(input())
ab=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ans=[-1]*n
cnt=0
node=[]
visited=[0]*n
ans=[-1]*n
def dfs(x):
	global cnt
	ans[x]=c[-cnt-1]
	visited[x]=1
	for next in ab[x]:
		if visited[next]==0:
			cnt+=1
			dfs(next)
dfs(0)
print(*ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**5*5)
n=int(input())
ab=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ans=[-1]*n
cnt=0
node=[]
visited=[0]*n
ans=[-1]*n
def dfs(x):
	global cnt
	ans[x]=c[-cnt-1]
	visited[x]=1
	for next in ab[x]:
		if visited[next]==0:
			cnt+=1
			dfs(next)
dfs(0)
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
A=list(map(int,input().split()))
b=[]
c=[]
for i in range(m):
 x,y=map(int,input().split())
 b.append(x)
 c.append(y) #入力
A.sort() 
for i in range(m):
 A.sort()
 if A[b[i]-1]<=c[i]:
  for k in range(b[i]):
   A[k]=c[i]
 else:
  for k in range(b[i]):
   if A[k] < c[i]:
    A[k]=c[i]
print(sum(A))

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[]
a.sort()
for i in range(m):
	x,y=map(int,input().split())
	bc.append([x,y])
bc.sort(key=lambda x:-x[1])
k=0
for i in range(n):
	if a[i]>=bc[k][1]:
		break
	elif bc[k][0]!=0:
		bc[k][0]-=1
		a[i]=bc[k][1]
	else:
		k+=1
		if k>=m:
			break
		elif a[i]<bc[k][1]:
			bc[k][0]-=1
			a[i]=bc[k][1]
		else:
			break
print(sum(a))
Buggy python submission (verdict: Runtime Error):
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=list(stack)[0]
	stack=set(stack)
	stack.remove(now)
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)



Fixed submission:
n,k=map(int,input().split())
s=input()
if s[k-1]=="A":
 d="a"
elif s[k-1]=="B":
 d="b"
else:
 d="c"
print(s[:k-1]+d+s[k:])
Buggy python submission (verdict: Runtime Error):
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
			new_now=pair[now][i][0]
	now=new_now
	stack.remove(now)
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)



Fixed submission:
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=stack.pop()
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=list(stack)[0]
	stack=set(stack)
	stack.remove(now)
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)



Fixed submission:
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=stack.pop()
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=list(stack)[0]
	stack=set(stack)
	stack.remove(now)
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)



Fixed submission:
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=stack.pop()
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
	for j in range(3001):
		if (n-r*i-g*j)%b==0 and \
		n-r*i-g*j>=0:
			ans+=1
print(ans)

Fixed submission:
r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
	for j in range(3001):
		if (n-r*i-g*j)%b==0 and \
		n-r*i-g*j>=0:
			ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
import math
gcd=a[0]
l=[]
r=[]
for i in range(n):
	gcd=math.gcd(gcd,a[i])
	l.append(gcd)
gcd=a[-1]
for i in range(n):
	gcd=math.gcd(gcd,a[-i-1])
	r.append(gcd)
x=list()
x.append((r[n-2]))
for i in range(n-2):
	x.append(math.gcd(l[i],r[n-i-3]))
x.append((l[n-2]))
print(max(x))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
import fractions
gcd=a[0]
l=[]
r=[]
for i in range(n):
	gcd=fractions.gcd(gcd,a[i])
	l.append(gcd)
gcd=a[-1]
for i in range(n):
	gcd=fractions.gcd(gcd,a[-i-1])
	r.append(gcd)
x=list()
x.append((r[n-2]))
for i in range(n-2):
	x.append(fractions.gcd(l[i],r[n-i-3]))
x.append((l[n-2]))
print(max(x))
Buggy python submission (verdict: Runtime Error):
m=int(input())
a=list(map(int,input().split()))
D=1
n=1

while n < m:
 if a[n] < max(a[0:n]):
  D=D 
  n=n+1
 else:
  D=D+1 
  n=n+1

print(D)

Fixed submission:
a,b=map(int,input().split())
print(max(2*a-1,2*b-1,a+b))
Buggy python submission (verdict: Time Limit Exceeded):
m=int(input())
a=list(map(int,input().split()))
D=1
n=1

while n < m:
 if a[n] < max(a[0:n]):
  D=D
 else:
  D=D+1

print(D)

Fixed submission:
m=int(input())
a=list(map(int,input().split()))
D=1
n=1

while n < m:
 if a[n] < max(a[0:n]):
  D=D 
  n=n+1
 else:
  D=D+1 
  n=n+1

print(D)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=input()
if "0" not in s:
	print(len(s))
	exit()
p=s[0]
a=[]
d=[]
b=[]
cnt_1=0
cnt_0=0
p=s[0]
for i in range(len(s)):
	if p!=s[i]:
		if p=="0":
			a.append(cnt_0)
			cnt_0=0
			p="1"
		else:
			b.append(cnt_1)
			cnt_1=0
			p="0"
	if s[i]=="0":
		cnt_0+=1
	else:
		cnt_1+=1
if cnt_0>0:
	a.append(cnt_0)
else:
	b.append(cnt_1)
if len(a)<=len(b):
	k+=1
	if len(a)==len(b):
		if s[0]=="0":
			b.insert(0,0)
		else:
			b.insert(-1,0)
	for i in range(len(b)-k+1):
		d.append(sum(b[i:i+k])+sum(a[i:i+k-1]))
else:
	b.insert(0,0)
	b.insert(len(b),0)
	for i in range(len(b)-k+1):
		k+=1
		d.append(sum(b[i:i+k])+sum(a[i:i+k-1]))
print(max(d))


Fixed submission:
n,k=map(int,input().split())
s=input()
cnt=[]
now=s[0]
p=0
for i in range(n):
	if s[i]==now:
		p+=1
	else:
		cnt.append(p)
		now=s[i]
		p=1
cnt.append(p)
ans=0
r=[]
cum_sum=0
for i in range(len(cnt)):
	cum_sum+=cnt[i]
	r.append((cnt[i],cum_sum))
for i in range(len(r)):
	if s[r[i][1]-r[i][0]]=="1":
		e=r[min(i+2*k,len(r)-1)][1]-r[i][1]+r[i][0]
	else:
		e=r[min(i+2*k-1,len(r)-1)][1]-r[i][1]+r[i][0]
	ans=max(ans,e)
print(ans)
Buggy python submission (verdict: Runtime Error):
a=input()
if a=A:
 print(T)
elif a=T:
 print(A)
elif a=C:
 print(G) 
else:
 print(C)

Fixed submission:
a=input()
if a=="A":
 print("T")
elif a=="T":
 print("A")
elif a=="C":
 print("G") 
else:
 print("C")
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
i=0
d=""
while i<n:
	if s[i]=="A" and s[i+1]=="C":
		d+="0"*2
		i+=2
	else:
		d+=s[i]
		i+=1
num=[0]*n
cnt=0
for i in range(n):
	if d[i]=="0":
		cnt+=1
	num[i]=cnt//2
for i in range(q):
	x,y=map(int,input().split())
	print(num[y-1]-num[x-1])


Fixed submission:
n,q=map(int,input().split())
s=input()
i=0
d=""
while i<n-1:
	if s[i]=="A" and s[i+1]=="C":
		d+="0"*2
		i+=2
	else:
		d+=s[i]
		i+=1
d+=s[-1]
num=[0]*n
cnt=0
for i in range(n):
	if d[i]=="0":
		cnt+=1
	num[i]=cnt//2
for i in range(q):
	x,y=map(int,input().split())
	print(num[y-1]-num[x-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
	a,b=map(int,input().split())
	cnt=0
	for i in range(a-1,b-1):
		if s[i]+s[i+1]=="AC":
			cnt+=1
	print(cnt)

Fixed submission:
n,q=map(int,input().split())
s=input()
i=0
d=""
while i<n-1:
	if s[i]=="A" and s[i+1]=="C":
		d+="0"*2
		i+=2
	else:
		d+=s[i]
		i+=1
d+=s[-1]
num=[0]*n
cnt=0
for i in range(n):
	if d[i]=="0":
		cnt+=1
	num[i]=cnt//2
for i in range(q):
	x,y=map(int,input().split())
	print(num[y-1]-num[x-1])
Buggy python submission (verdict: Runtime Error):
=int(input())
c=[]
a=[]
b=[]
for i in range(n):
	x,y=map(int,input().split())
	a.append(x)
	b.append(y)
	c.append([x-y,i])
c.sort()
c.reverse()
q=[]
qq=[]
for i in range(n):
	if i%2==0:
		q.append(c[i][1])
	else:
		qq.append(c[i][1])
ans=0
for i in range(len(q)):
	ans+=a[q[i]]
for i in range(len(qq)):
	ans-=b[qq[i]]
print(ans)
	

Fixed submission:
n=int(input())
ans=0
c=[]
for i in range(n):
	x,y=map(int,input().split())
	ans+=x
	c.append(x+y)
c.sort()
c.reverse()
for i in range(n):
	if i%2!=0:
		ans-=c[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]
for i in range(1,n):
	p=10**12
	for j in range(k):
		if j>=i:
			break
		else:
			p=min(p,dp[i-j-1]+abs(h[i]-h[i-j-1]))
	dp.append(p)
print(dp[-1])

Fixed submission:
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]
for i in range(1,n):
	p=10**12
	for j in range(k):
		if j>=i:
			break
		else:
			p=min(p,dp[i-j-1]+abs(h[i]-h[i-j-1]))
	dp.append(p)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
print(dp[-1][-1])


Fixed submission:
n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
print(dp[-1][-1])