Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = [int(x) for x in input().split()]
t = lcm(A)

mod = 10**9+7
ans = 0
for i in range(N):
    ans = (ans + t//A[i])%mod

print(ans)


Fixed submission:
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    t = 1
    for n in numbers:
        t = lcm_base(t, n)
    return t

N = int(input())
A = [int(x) for x in input().split()]

mod = 10**9+7
ans = 0
t = lcm(A)
t %= mod
for i in range(N):
    ans = (ans + t*pow(A[i],mod-2, mod))%mod

print(ans)

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = [int(x) for x in input().split()]
t = lcm(A)

mod = 10**9+7
ans = 0
for i in range(N):
    ans = (ans + t//A[i])%mod

print(ans)


Fixed submission:
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(numbers):
    t = 1
    for n in numbers:
        t = lcm_base(t, n)
    return t

N = int(input())
A = [int(x) for x in input().split()]

mod = 10**9+7
ans = 0
t = lcm(A)
t %= mod
for i in range(N):
    ans = (ans + t*pow(A[i],mod-2, mod))%mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod


N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

mod = 10**9+7

l = [[A[0], comb(N-1, K-1, mod=mod)]]
r = [[A[-1], comb(N-1, K-1, mod=mod)]]


for i in range(1,N):
	if N-i-1>=K-1:
		l.append([A[i], comb(N-i-1, K-1,mod=mod)])
for i in range(N-1)[::-1]:
	if i>=K-1:
		r.append([A[i],comb(i, K-1,mod=mod)])


s = 0
t = 0

for i,j in l:
	s = (s+(i*j)%mod)%mod

for i,j in r:
	t = (t+(i*j)%mod)%mod

ans = (t-s)%mod
if ans < 0:
	ans += mod
print(ans)


Fixed submission:


N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

mod = 10**9+7


l = 0
r = 0
t = 1
cnt = 1
for i in range(N-K+1)[::-1]:
	l = (l+(t*A[i])%mod)%mod
	t = (t*(cnt+K-1))%mod
	t = (t*pow(cnt,mod-2, mod))%mod
	cnt+=1
t = 1
cnt = 1
for i in range(K-1, N):
	r = (r+(t*A[i])%mod)%mod
	t = (t*(cnt+K-1))%mod
	t = (t*pow(cnt,mod-2, mod))%mod
	cnt+=1


ans = (r-l)%mod
if ans < 0:
	ans += mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod


N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

mod = 10**9+7

l = [[A[0], comb(N-1, K-1, mod=mod)]]
r = [[A[-1], comb(N-1, K-1, mod=mod)]]


for i in range(1,N):
	if N-i-1>=K-1:
		l.append([A[i], comb(N-i-1, K-1,mod=mod)])
for i in range(N-1)[::-1]:
	if i>=K-1:
		r.append([A[i],comb(i, K-1,mod=mod)])


s = 0
t = 0

for i,j in l:
	s = (s+(i*j)%mod)%mod

for i,j in r:
	t = (t+(i*j)%mod)%mod

ans = (t-s)%mod
if ans < 0:
	ans += mod
print(ans)


Fixed submission:


N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

mod = 10**9+7


l = 0
r = 0
t = 1
cnt = 1
for i in range(N-K+1)[::-1]:
	l = (l+(t*A[i])%mod)%mod
	t = (t*(cnt+K-1))%mod
	t = (t*pow(cnt,mod-2, mod))%mod
	cnt+=1
t = 1
cnt = 1
for i in range(K-1, N):
	r = (r+(t*A[i])%mod)%mod
	t = (t*(cnt+K-1))%mod
	t = (t*pow(cnt,mod-2, mod))%mod
	cnt+=1


ans = (r-l)%mod
if ans < 0:
	ans += mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(x) for x in input().split()]
A.sort()

mod = 10**9 + 7
ans = 0
k=1
while A[-1]>0:
    t = 0
    for i in range(N):
        t+=A[i]%2
        A[i]//=2
    ans = (ans + (N-t)*t*(2**(k-1))%mod)%mod
    k +=1
print(ans)


Fixed submission:
N=int(input())
A=[int(x) for x in input().split()]
A.sort()

mod = 10**9 + 7
def mulmod(s):
    r = 1
    for i in s:
        r = r*i%mod
    return r


ans = 0
k=1
while A[-1]>0:
    t = 0
    for i in range(N):
        t+=A[i]%2
        A[i]//=2
    r = [N-t, t, pow(2, k-1, mod)]
    ans = (ans + mulmod(r))%mod
    k +=1
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append([b,i])
    G[b].append([a,i])

def bfs(x, c, b):
    if seen[x]:
        return
    seen[x] = True
    if b!=-1:
        global k
        color[b] = c
        k = max(k,c)
    t = 1
    for i,b in G[x]:
        if t==c:
            t+=1
        if not(seen[i]):
            bfs(i,t,b)
            t+=1

seen = [False]*N
color = [0]*N
k=0
bfs(0, 0, -1)


print(k)
print(*color[:-1],sep='\n')


Fixed submission:
import sys
sys.setrecursionlimit(10**6)

N=int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].append([b,i])
    G[b].append([a,i])

def bfs(x, c, b):
    if seen[x]:
        return
    seen[x] = True
    if b!=-1:
        global k
        color[b] = c
        k = max(k,c)
    t = 1
    for i,b in G[x]:
        if t==c:
            t+=1
        if not(seen[i]):
            bfs(i,t,b)
            t+=1

seen = [False]*N
color = [0]*N
k=0
bfs(0, 0, -1)


print(k)
print(*color[:-1],sep='\n')
Buggy python submission (verdict: Runtime Error):
import math

a,b,x = map(int,input().split())


if a*a*b>2*x:
	print(90- math.atan(2*x/(a*b*b) *360/(2*math.pi)))
else:
	print(90- math.atan(a**3/(2*(a*a*b-x))) *360/(2*math.pi))

Fixed submission:
import math

a,b,x = map(int,input().split())


if a*a*b>2*x:
	print(90- math.atan2(2*x, a*b*b) *360/(2*math.pi))
else:
	print(90- math.atan2(a**3, 2*(a*a*b-x)) *360/(2*math.pi))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

ans=0
for i in range(N-2):
	for j in range(i+1,N-1):
		p = A[i]+A[j]
		ans += bisect.bisect_left(A[j+1:],p)

print(ans)

Fixed submission:
from bisect import bisect_left

N = int(input())
L = [int(x) for x in input().split()]
L.sort()

ans = 0
for i in range(N-2):
	for j in range(i+1,N-1):
		ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N-1)]
A.sort()
B=[list(map(int,input().split())) for _ in range(Q)]
B.sort()

cost=[0]*(N+1)

for b in B:
	cost[b[0]]+=b[1]

for a in A:
	cost[a[1]] += cost[a[0]]
print(*cost[1:])

Fixed submission:
N,Q=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N-1)]
A.sort()

cost=[0]*(N+1)

for _ in range(Q):
	a,b=map(int,input().split())
	cost[a]+=b

for a in A:
	cost[a[1]] += cost[a[0]]
print(*cost[1:])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[''.join(sorted(input())) for i in range(N)]
B=list(map(A.count,set(A)))

ans=0
for b in B:
    if b==2:ans+=1
    else:ans+=b*(b-1)//2
print(ans)



Fixed submission:
N=int(input())
d={}
for i in range(N):
    l=[0]*26
    for s in input():
        l[ord(s)-97]+=1
    l=tuple(l)
    if l in d:d[l]+=1
    else:d[l]=1

ans=0
for c in d:
    if d[c]==2:ans+=1
    elif d[c]!=1:ans+=d[c]*(d[c]-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
A = []
B = []
N = int(input())

for i in range(N):
	t = input()
	t = sorted(t)
	
	flag = True
	for i in range(len(A)):
		if A[i] == t:
			B[i] += 1
			flag = False
			break
	
	if flag:
		A.append(t)
		B.append(1)
		
ans = 0
for b in B:
	if b==2:
		ans += 1
	elif b!=1:
		t = 1
		for i in range(2,b+1):
			t*=i
		ans += int(t/2)
		
print(ans)

Fixed submission:
N=int(input())
d={}
for i in range(N):
    l=[0]*26
    for s in input():
        l[ord(s)-97]+=1
    l=tuple(l)
    if l in d:d[l]+=1
    else:d[l]=1

ans=0
for c in d:
    if d[c]==2:ans+=1
    elif d[c]!=1:ans+=d[c]*(d[c]-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

t=[]
ans=0
for i in range(M)[::-1]:
    t+=d[i]
    ans+=max(t)
    t.remove(max(t))
print(ans)

Fixed submission:
import heapq

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

hq=[]
ans=0
for i in range(M)[::-1]:
    [heapq.heappush(hq,-j) for j in d[i]]
    ans-=heapq.heappop(hq)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(x) for x in input().split()]

A = [[] for i in range(M)]

for i in range(N):
	t1, t2 = [int(x) for x in input().split()]
	if t1-1 <= M-1:
		A[t1-1].append(t2)


ans = 0
for i in range(M):
	t = 0
	idx = -1
	for j in range(i+1):
		if A[j] != []:
			if max(A[j]) >= t:
				idx = j
				t = max(A[j])
	if idx!=-1:
		ans += t
		A[idx].remove(t)


print(ans)



Fixed submission:
import heapq

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

hq=[]
ans=0
for i in range(M)[::-1]:
    [heapq.heappush(hq,-j) for j in d[i]]
    ans-=heapq.heappop(hq)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(x) for x in input().split()]

A = [[] for i in range(M)]

for i in range(N):
	t1, t2 = [int(x) for x in input().split()]
	if t1-1 <= M-1:
		A[t1-1].append(t2)


ans = 0
for i in range(M):
	t = 0
	idx = -1
	for j in range(i+1):
		if A[j] != []:
			if max(A[j]) >= t:
				idx = j
				t = max(A[j])
	if idx!=-1:
		ans += t
		A[idx].remove(t)


print(ans)


Fixed submission:
import heapq

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

hq=[]
ans=0
for i in range(M)[::-1]:
    [heapq.heappush(hq,-j) for j in d[i]]
    ans-=heapq.heappop(hq)
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

t = [int(x) for x in input().split()]

t = np.array(t).reshape(N, 1)
A = np.eye(N, N)
A[:-1, :] += A[1:, :]
A[N-1, 0] = 1

t = 2*np.dot(np.linalg.inv(A), t)

for i in range(N-1):
	print(int(t[i]), end=' ')
print(int(t[N-1]))



Fixed submission:
N=int(input())
X=list(map(int,input().split()))
Y=[0]*N
S=sum(X)

Y[0]=S-2*sum([X[i] for i in range(N) if i%2==1])

for i in range(N-1):
	Y[i+1]=2*X[i]-Y[i]

print(*Y)

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

t = [int(x) for x in input().split()]

t = np.array(t)

A = np.zeros((N, N))

for i in range(N-1):
	A[i, i] = 1
	A[i, i+1] = 1
A[N-1, N-1] = 1
A[N-1, 0] = 1

t = 2*np.dot(np.linalg.inv(A), t)

for i in range(N-1):
	print(int(t[i]), end=' ')
print(int(t[N-1]))

Fixed submission:
N=int(input())
X=list(map(int,input().split()))
Y=[0]*N
S=sum(X)

Y[0]=S-2*sum([X[i] for i in range(N) if i%2==1])

for i in range(N-1):
	Y[i+1]=2*X[i]-Y[i]

print(*Y)
Buggy python submission (verdict: Runtime Error):
import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))


Fixed submission:
N = input()

ans = 'Good'
for i in range(len(N)-1):
	if N[i] == N[i+1]:
		ans='Bad'
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)/math.gcd(A, D)
A = A-1

if A == 0:
	t1 = 0
else:
	t1 = A - (A/C + A/D - A/lcm)

t2 = B - (B/C + B/D - B/lcm)
print(int(t2 - t1))


Fixed submission:
import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))

Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//math.gcd(A, D)
A = A-1

if A == 0:
	t1 = 0
else:
	t1 = A - (A//C + A//D - A//lcm)

t2 = B - (B//C + B//D - B//lcm)
print(t2 - t1)


Fixed submission:
import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))

Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//math.gcd(A, D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(t2 - t1)


Fixed submission:
import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
A = np.zeros((N,2))

for i in range(N):
	A[i, 0], A[i, 1] = [int(j) for j in input().split()]

A = A[np.argsort(A[:,1]), :]

for i in range(N-1):
	A[i+1, 0] = A[i, 0]+A[i+1, 0]

ans = ['Yes', 'No']
print(ans[np.sum((A[:,1]-A[:,0])<0)])


Fixed submission:
import numpy as np

N = int(input())
A = np.zeros((N,2))

for i in range(N):
	A[i, 0], A[i, 1] = [int(j) for j in input().split()]

A = A[np.argsort(A[:,1]), :]

for i in range(N-1):
	A[i+1, 0] = A[i, 0]+A[i+1, 0]

ans = ['Yes', 'No']
t = np.sum((A[:,1]-A[:,0])<0)

print(ans[t>0])
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
dp=[0]*(N+1)
idx=0
dp[0]=1
if A[idx]==1:
    dp[1]=0
    if M>1:idx+=1
else:
    dp[1]=1

for i in range(2,N+1):
    if A[idx]==i:
        dp[i]=0
        if idx+1<M:idx+=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Fixed submission:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]

dp=[-1]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
if dp[1]==-1:dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
dp=[0]*(N+1)
idx=0
dp[0]=1
if A[idx]==1:
    dp[1]=0
    if M>1:idx+=1
else:
    dp[1]=1

for i in range(2,N+1):
    if A[idx]==i:
        dp[i]=0
        if idx+1<M:idx+=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Fixed submission:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]

dp=[-1]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
if dp[1]==-1:dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort()
idx=0
for i in range(M):
	b,c=map(int,input().split())
	t=bisect.bisect_left(A,c)
	if t>0:
		[bisect.insort_left(A,c) for i in range(min(t,b))]
		A=A[min(t,b):]

print(sum(A))

Fixed submission:
N,M=map(int,input().split())
A=[]
[A.append([int(i),1]) for i in input().split()]
for i in range(M):
	A.append(list(map(int,input().split()))[::-1])
A.sort(reverse=True)
cnt=0
ans=0
for a in A:
	if N<=(cnt+a[1]):
		ans+=(N-cnt)*a[0]
		break
	else:
		ans+=a[0]*a[1]
		cnt+=a[1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

d=[-1]*(N+1)
d[0]=0
d[1]=0

A=[list(map(int,input().split())) for i in range(N-1)]

nlist=[]

def search(A,nlist):
	global d	
	t=[]
	for ne in nlist:
		for a,b,w in A:
			if a==ne and d[b]==-1:
				d[b]=d[a] if w%2==0 else (d[a]+1)%2
				t.append(b)
			if b==ne and d[a]==-1:
				d[a]=d[b] if w%2==0 else (d[b]+1)%2
				t.append(a)
	
	if t!=[]:
		search(A,t)

search(A,[1])
print(*d[1:],sep='\n')

Fixed submission:
N=int(input())

graph=[[] for i in range(N+1)]

for i in range(N-1):
	a,b,w=map(int,input().split())
	graph[a].append([b,w])
	graph[b].append([a,w])


color=[-1]*(N+1)
color[1]=0

ne=[1]

while ne!=[]:
	t=ne.pop()
	for s,w in graph[t]:
		if color[s]==-1:
			ne.append(s)
			color[s]=color[t] if w%2==0 else (color[t]+1)%2

print(*color[1:],sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[[] for i in range(N-1)]
for i in range(N-1):
	A[i]=list(map(int,input().split()))
	A[i][2]%=2
A.sort()

ans=[0]*(N+1)
his=[False for i in range(N+1)]
his[0]=True
his[1]=True
idx=1


def search(A,his,ans,idx):
	if all(his):
		return
	for a in A:
		if idx in a[:2]:
			next_idx=a[(a[:2].index(idx)+1)%2]
			if his[next_idx]==False:
				ans[next_idx]=ans[idx]
				if a[2]!=0:
					ans[next_idx]+=1
					ans[next_idx]%=2
				his[next_idx]=True
				search(A,his,ans,next_idx)
				his[next_idx]=False

search(A,his,ans,idx)
print(*ans[1:],sep='\n')


Fixed submission:
N=int(input())

graph=[[] for i in range(N+1)]

for i in range(N-1):
	a,b,w=map(int,input().split())
	graph[a].append([b,w])
	graph[b].append([a,w])


color=[-1]*(N+1)
color[1]=0

ne=[1]

while ne!=[]:
	t=ne.pop()
	for s,w in graph[t]:
		if color[s]==-1:
			ne.append(s)
			color[s]=color[t] if w%2==0 else (color[t]+1)%2

print(*color[1:],sep='\n')
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
s=input()

A=[]

if s[0]!='1':A.append(0)

cnt=1
pre=s[0]
for i in s[1:]:
	if pre!=i:
		A.append(cnt)
		cnt=1
		pre=i
	else:
		cnt+=1

if (s[-1]=='1' and len(A)%2==0) or (s[-1]=='0' and len(A)%2!=0):
	A.append(cnt)


if s[-1]!='0':
	A.append(0)
A.append(0)

dp=[0]*(len(A)//2-K+1)

for i in range(2*K+1):dp[0]+=A[i]

i=1
idx=0
while len(dp)>i:
	dp[i]=dp[i-1]-A[idx]-A[idx+1]+A[idx+2*(K+1)]+A[idx-1+2*(K+1)]
	idx+=2
	i+=1

print(max(dp))

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

A=[]

if s[0]!='1':A.append(0)

cnt=1
pre=s[0]
for i in s[1:]:
	if pre!=i:
		A.append(cnt)
		cnt=1
		pre=i
	else:
		cnt+=1

if (s[-1]=='1' and len(A)%2==0) or (s[-1]=='0' and len(A)%2!=0):
	A.append(cnt)


if s[-1]!='0':
	A.append(0)
A.append(0)

dp=[0]*(len(A)//2-K+1)

if (2*K+1)>=len(A):print(sum(A))
else:
	for i in range(2*K+1):dp[0]+=A[i]
	
	i=1
	idx=0
	while len(dp)>i:
		dp[i]=dp[i-1]-A[idx]-A[idx+1]+A[idx+2*(K+1)]+A[idx-1+2*(K+1)]
		idx+=2
		i+=1
	
	print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
import re
n,q=map(int,input().split())
s=input()
ans=[0]*q
for i in range(q):
    l,r=map(int,input().split())
    ans[i]=len(re.findall('(AC)',s[l-1:r]))
print(*ans,sep='\n')


Fixed submission:
n,q=map(int,input().split())
s=input()
l=[0]*(len(s)+1)
for i in range(1,len(s)):
    l[i+1]=l[i]
    if s[i-1]=='A' and s[i]=='C':
        l[i+1]+=1
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    ans[i]=l[b]-l[a]
print(*ans,sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
s=input()
for _ in range(Q):
    l,r=map(int,input().split())
    print(s[l-1:r].count('AC'))

Fixed submission:
n,q=map(int,input().split())
s=input()
l=[0]*(len(s)+1)
for i in range(1,len(s)):
    l[i+1]=l[i]
    if s[i-1]=='A' and s[i]=='C':
        l[i+1]+=1
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    ans[i]=l[b]-l[a]
print(*ans,sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
import re

N,Q=map(int,input().split())
s=input()
for _ in range(Q):
    l,r=map(int,input().split())
    print(len(re.findall('AC',s[l-1:r])))

Fixed submission:
n,q=map(int,input().split())
s=input()
l=[0]*(len(s)+1)
for i in range(1,len(s)):
    l[i+1]=l[i]
    if s[i-1]=='A' and s[i]=='C':
        l[i+1]+=1
ans=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    ans[i]=l[b]-l[a]
print(*ans,sep='\n')
Buggy python submission (verdict: Runtime Error):
import numpy as np

x1,y1,x2,y2 = map(int,input().split())

a=np.array([x1,y1])
b=np.array([x2,y2])

T = np.array([[0,-1],[1,0]])

c = b + np.dot(T,b-a)
d = c + np.dot(T,c-b)
print(*c,*d)

Fixed submission:
import numpy as np

x1,y1,x2,y2 = map(int,input().split())

a=np.array([x1,y1])
b=np.array([x2,y2])

T = np.array([[0,-1],[1,0]])

c = b + np.dot(T,b-a)
d = c + np.dot(T,c-b)
print(*c, end=' ')
print(*d)
Buggy python submission (verdict: Runtime Error):
import bisect

N, K =map(int,input().split())
X = [int(x) for x in input().split()]

l = []
r = []
for x in X:
  if x<0:
    l.append(-x)
  else:
    r.append(x)
l = l[::-1]


sl = 2*10**8
sr = 2*10**8
sa = 2*10**8

if len(l)>=K:
  sl = l[K-1]
if len(r)>=K:
  sr = r[K-1]

if len(l)!=0 and len(r)!=0:
  il = 0
  ir = 0
  while not(il+ir+2>=K):
    if il>=len(l)-1:
      ir += 1
    elif ir>=len(r)-1:
      il += 1
    else:
      if l[il+1]<l[ir+1]:
        il+=1
      else:
        ir+=1
  sa = l[il] + r[ir] +min(l[il],r[ir])

print(min([sl, sr, sa]))


Fixed submission:
N, K = map(int,input().split())
A = [int(x) for x in input().split()]

ans = 3*10**8 + 1
for i in range(N-K+1):
  l = A[i]
  r = A[i+K-1]
  a = abs(l) + r-l
  b = abs(r) + r-l
  ans = min(ans, min(a,b))
print(ans)
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
A=[input() for i in range(H)]

for i in range(H):
	for j in range(W):
		if A[i][j]=='#':
			f=False
			for a,b in [(-1,0),(1,0),(0,1),(0,-1)]:
				if 0<=i+a<H and 0<=j+b<W:
					if A[i+a][j+b]=='#':f=True
			if not(f):break

print('Yes' if f else 'No')

Fixed submission:
H,W=map(int,input().split())
A=[input() for i in range(H)]

f=True
for i in range(H):
	for j in range(W):
		if A[i][j]=='#':
			g=False
			for a,b in [(-1,0),(1,0),(0,1),(0,-1)]:
				if 0<=i+a<H and 0<=j+b<W:
					if A[i+a][j+b]=='#':g=True
			if not(g):f=False

print('Yes' if f else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
a,b,x=map(int,input().split())
A=set(range(a,a+x))|set(range(b-x+1,b+1))
r=set(range(a,b+1))
print(*sorted(A&r),sep='\n')

Fixed submission:
a,b,x=map(int,input().split())
A=sorted(set(range(a,min(a+x,b+1)))|set(range(max(b-x+1,a),b+1)))
print(*A,sep='\n')
Buggy python submission (verdict: Runtime Error):
from sys import exit

N = int(input())
A = [int(x) for x in input().split()]

m1 = 0
m2 = 0
m4 = 0

for a in A:
	if a%4==0:
		m4 += 1
	elif a%2==0:
		m2 += 1
	else:
		m1 += 1


m1 = m1 + (m2>0)
if m4>=m1-1:
	print('Yes')
else:
	print('No')

Fixed submission:
N, M = map(int,input().split())
t = (N-M)*100 + M*1900
print(2**M*t)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
s=set([])
for i in range(N):
    s=s^{int(input())}
print(len(s))


Fixed submission:
N=int(input())
A=[int(input()) for _ in range(N)]
d={}
for a in A:d[a]=0
for a in A:d[a]+=1
cnt=0
for i in d:
    if d[i]%2:cnt+=1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(input()) for _ in range(N)]
A=list(map(A.count, set(A)))
ans=0
for a in A:
    if a%2:ans+=1
print(ans)

Fixed submission:
N=int(input())
A=[int(input()) for _ in range(N)]
d={}
for a in A:d[a]=0
for a in A:d[a]+=1
cnt=0
for i in d:
    if d[i]%2:cnt+=1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
s=set([])
for i in range(N):
    s=s^{int(input())}
print(len(s))

Fixed submission:
N=int(input())
A=[int(input()) for _ in range(N)]
d={}
for a in A:d[a]=0
for a in A:d[a]+=1
cnt=0
for i in d:
    if d[i]%2:cnt+=1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

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

max_val = max(A)

while True:
	flag = True
	for a in A:
		if max_val%a != 0:
			flag = False
			break
	if flag:
		break
	max_val += max_val

print(max_val)

Fixed submission:
from fractions import gcd
from functools import reduce

N=int(input())
T =[int(input()) for i in range(N)]
print(reduce(lambda x,y:x*y//gcd(x,y), T))