Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())
N,M,P=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    ABC[i][2]=-1*(ABC[i][2]-P)

idle_max=10**9
data=[idle_max for i in range(N+1)]
data[1]=0

for i in range(N-1):
    for a,b,c in ABC:
        if data[a] != idle_max:
            data[b]=min(data[b],data[a]+c)
value=data[N]
for i in range(N):
    for a,b,c in ABC:
        if data[a] != idle_max:
            data[b]=min(data[b],data[a]+c)
if data[N]!=value:
    print(-1)
else:
    print(max(-value,0))


Fixed submission:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())
N,M,P=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    ABC[i][2]=-1*(ABC[i][2]-P)
data=[[] for i in range(N+1)]
for a,b,c in ABC:
    data[b].append(a)

idle_max=10**9




visited=set()
stack=[N]
while stack:
    a=stack.pop()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append(p)




data=[idle_max for i in range(N+1)]
data[1]=0
for i in range(N-1):
    for a,b,c in ABC:
        if data[a] != idle_max:
            data[b]=min(data[b],data[a]+c)
predata=copy.copy(data)
value=data[N]
for i in range(N):
    for a,b,c in ABC:
        if data[a] != idle_max:
            data[b]=min(data[b],data[a]+c)

for i in visited:
    if predata[i]>data[i]:
        break
else:
    print(max(-value,0))
    exit()
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m in range(len(S))]
mod=10**9+7
if S[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(S[0])]+=1
for i in range(1,len(S)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
#print(dp)
print(dp[-1][5]%mod)


Fixed submission:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m in range(len(S))]
mod=10**9+7
if S[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(S[0])]+=1
for i in range(1,len(S)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
    for m in range(13):
        dp[i][m]%=mod
#print(dp)
print(dp[-1][5]%mod)
Buggy python submission (verdict: Runtime Error):
S=int(input())

if S<10**18:
    X1,Y1=0,0

    mod=10**9

    X2=mod
    Y3=S//mod + 1

    Y2=1
    X3=mod-S%mod
else:
    X1,Y1,X2,Y3=0,0,0,0
    Y2=10**9
    Y3=10**9

print(X1,Y1,X2,Y2,X3,Y3)


Fixed submission:
S=int(input())

if S<10**18:
    X1,Y1=0,0

    mod=10**9

    X2=mod
    Y3=S//mod + 1

    Y2=1
    X3=mod-S%mod
else:
    X1,Y1,X2,Y3=0,0,0,0
    Y2=10**9
    X3=10**9

print(X1,Y1,X2,Y2,X3,Y3)

Buggy python submission (verdict: Runtime Error):
S=int(input())

if S<10**18
    X1,Y1=0,0

    mod=10**9

    X2=mod
    Y3=S//mod + 1

    Y2=1
    X3=mod-S%mod
else:
    X1,Y1,X2,Y3=0,0,0,0
    Y2=10**9
    Y3=10**9

print(X1,Y1,X2,Y2,X3,Y3)


Fixed submission:
S=int(input())

if S<10**18:
    X1,Y1=0,0

    mod=10**9

    X2=mod
    Y3=S//mod + 1

    Y2=1
    X3=mod-S%mod
else:
    X1,Y1,X2,Y3=0,0,0,0
    Y2=10**9
    X3=10**9

print(X1,Y1,X2,Y2,X3,Y3)
Buggy python submission (verdict: Runtime Error):
A,B,C,D=list(map(int,input().split()))
def Factoring(value):
    _value=value
    div=2
    data=[]
    while value!=1:
        while value%div==0:
            value=int(value/div)
            data.append(div)
        div+=1
    return(data)
def divcheck(value,lst):
    for i in lst:
        if value%i!=0:
            return(1)
        value=int(value/i)
    return(0)
FactoringC,FactoringD=Factoring(C),Factoring(D)
for i in range(A,B+1):
    if not divcheck(i,FactoringC):
        startC=i
        break
for i in range(A,B+1):
    if not divcheck(i,FactoringD):
        startD=i
        break
print(B+1-A-len(set(list(range(startC,B+1,C))+list(range(startD,B+1,D)))))


Fixed submission:
from fractions import Fraction ,gcd
def lcm(a,b):
    return(a*b//gcd(a,b))
A,B,C,D=map(int,input().split())
N=B-A+1
ans=N- (B//C + B//D - (A-1)//C - (A-1)//D) + B//(lcm(C,D)) -(A-1)//(lcm(C,D))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
A,B,C,D=list(map(int,input().split()))
print(len([i for i in range(A,B+1) if i%C!=0 and i%D!=0]))


Fixed submission:
from fractions import Fraction ,gcd
def lcm(a,b):
    return(a*b//gcd(a,b))
A,B,C,D=map(int,input().split())
N=B-A+1
ans=N- (B//C + B//D - (A-1)//C - (A-1)//D) + B//(lcm(C,D)) -(A-1)//(lcm(C,D))
print(ans)
Buggy python submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())
if x=W/2 and y=H/2:
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W)),0)
"""else:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W),min(H*H*x/y,H*W-H*H*x/y),min(W*W*y/x,H*W-W*W*y/x)),0)"""


Fixed submission:
W,H,x,y=map(int,input().split())
if x==W/2 and y==H/2:
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(W*H/2,0)

Buggy python submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())
if x=W/2 and y=H/2
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W)),0)
"""else:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W),min(H*H*x/y,H*W-H*H*x/y),min(W*W*y/x,H*W-W*W*y/x)),0)"""


Fixed submission:
W,H,x,y=map(int,input().split())
if x==W/2 and y==H/2:
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(W*H/2,0)

Buggy python submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())
if x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,1)
elif x and y:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W)),0)
else:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W),min(H*H*x/y,H*W-H*H*x/y),min(W*W*y/x,H*W-W*W*y/x)),0)


Fixed submission:
W,H,x,y=map(int,input().split())
if x==W/2 and y==H/2:
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(W*H/2,0)

Buggy python submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())
if x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,1)
else:
    print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W),min(H*H*x/y,H*W-H*H*x/y),min(W*W*y/x,H*W-W*W*y/x)),0)


Fixed submission:
W,H,x,y=map(int,input().split())
if x==W/2 and y==H/2:
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(W*H/2,0)

Buggy python submission (verdict: Runtime Error):
W,H,x,y=map(int,input().split())
print(max(min(x*H,(W-x)*H),min(y*W,(H-y)*W)),sum([x/W==y/H,x/W==(H-y)/H,(W-x)/W==y/H])=>1)


Fixed submission:
W,H,x,y=map(int,input().split())
if x==W/2 and y==H/2:
    print(W*H/2,1)
elif not x or not y:
    print(W*H/2,0)
elif x/W==y/H or x/W==(H-y)/H:
    print(W*H/2,0)
else:
    print(W*H/2,0)
Buggy python submission (verdict: Runtime Error):
S=input()
mod=10**9 + 7
dp=[[0,0,0] for i in range(len(S))]
dp[0][0]=2
dp[0][2]=1

for i in range(1,len(S)):
   if S[i]=="1":
      dp[i][0]+=dp[i-1][0]* 2 % mod  
      dp[i][2]+=dp[i-1][0]* 1 % mod 
   else:
      dp[i][0]+=dp[i-1][0]* 1 % mod 
   dp[i][1]+=(dp[i-1][1]+dp[i-1][2]) * 2 % mod
   dp[i][2]+=(dp[i-1][1]+dp[i-1][2]) * 1 % mod                 
   dp[i][0]%=mod             
   dp[i][1]%=mod
   dp[i][2]%=mod
value=(dp[i][0]+dp[i][1]+dp[i][2])%mod
print(value)
            
                 
   

Fixed submission:
S=input()
mod=10**9 + 7
dp=[[0,0,0] for i in range(len(S))]
dp[0][0]=2
dp[0][2]=1

for i in range(1,len(S)):
   if S[i]=="1":
      dp[i][0]+=dp[i-1][0]* 2 % mod  
      dp[i][2]+=dp[i-1][0]* 1 % mod 
   else:
      dp[i][0]+=dp[i-1][0]* 1 % mod 
   dp[i][1]+=(dp[i-1][1]+dp[i-1][2]) * 2 % mod
   dp[i][2]+=(dp[i-1][1]+dp[i-1][2]) * 1 % mod                 
   dp[i][0]%=mod             
   dp[i][1]%=mod
   dp[i][2]%=mod
value=(dp[-1][0]+dp[-1][1]+dp[-1][2])%mod
print(value)
Buggy python submission (verdict: Runtime Error):
S=input()

i=0
T=[]
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T.append("D")
        i+=2
    else:
        T+=append(S[i])
        i+=1
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



#print(T)
print(count)


Fixed submission:
S=input()

i=0
T=[]
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T.append("D")
        i+=2
    else:
        T.append(S[i])
        i+=1
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



#print(T)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()

i=0
T=""
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T+="D"
        i+=2
    else:
        T+=S[i]
        i+=1
T=list(T)
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



#print(T)
print(count)


Fixed submission:
S=input()

i=0
T=[]
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T.append("D")
        i+=2
    else:
        T.append(S[i])
        i+=1
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



#print(T)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()

i=0
T=""
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T+="D"
        i+=2
    else:
        T+=S[i]
        i+=1
T=list(T)
count=0
count2=-1
m=0
#print(T)
while count!=count2:

    count2=count
    flag=0
    for i in range(m,len(T)-1):
        if "A"==T[i] and "D" == T[i+1]:
            T[i]="D"
            T[i+1]="A"
            count+=1
            """if flag==0:
                m=i
                flag=1"""
        #print(T)
print(count)


Fixed submission:
S=input()

i=0
T=[]
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T.append("D")
        i+=2
    else:
        T.append(S[i])
        i+=1
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



#print(T)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()

i=0
T=""
while i<len(S):
    if S[i]=="A":
        T+=S[i]
    elif i+1<len(S) and S[i]+S[i+1]=="BC":
        T+="D"

count=0
count2=-1
while count!=count2:
    count2=count
    for i in range(len(S)-1):
        if "AD"==S[i]+S[i+1]:
            S[i],S[i+1]="D","A"
            count+=1
print(count)


Fixed submission:
S=input()

i=0
T=[]
while i<len(S):

    if i+1<len(S) and S[i]+S[i+1]=="BC":
        T.append("D")
        i+=2
    else:
        T.append(S[i])
        i+=1
count=0
m=0
Acount=0
#print(T)
for i in range(len(T)):
    if "A"==T[i]:
        Acount+=1
    elif "D"==T[i]:
        count+=Acount
    else:
        Acount=0



#print(T)
print(count)
Buggy python submission (verdict: Runtime Error):
X=[input() for i in range(2)]
A,P=X[0],X[1]

print(int(A*3+P)/2)


Fixed submission:
X=input()
X=X.split()
A,P=int(X[0]),int(X[1])

print(int((A*3+P)/2))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
switch_list=[input().split() for i in range(M)]
switch_list=[[int(i[m+1]) for m in range(len(i)-1)] for i in switch_list]
P_list=input().split()
P_list=[int(i) for i in P_list]
for i in range(1 << z):
    switch=[0 for i in range(N)]
    for j in range(z):
        if ((i >> j) & 1) == 1:
            switch[j]=1
    count+=sum([sum([switch[m-1] for m in switch_list[x]])%2==P_list[x] for x in range(M)])==M
print(count)


Fixed submission:
N, M = map(int, input().split())
switch_list=[input().split() for i in range(M)]
switch_list=[[int(i[m+1]) for m in range(len(i)-1)] for i in switch_list]
P_list=input().split()
P_list=[int(i) for i in P_list]
count=0
z=N
for i in range(1 << z):
    switch=[0 for i in range(N)]
    for j in range(z):
        if ((i >> j) & 1) == 1:
            switch[j]=1
    count+=sum([sum([switch[m-1] for m in switch_list[x]])%2==P_list[x] for x in range(M)])==M
print(count)
Buggy python submission (verdict: Runtime Error):
A,B=map(int,input().split())
if A=<5:
  print(0)
elif 6<=A<=12:
  print(B/2)
elif A>=13:
  print(B)

Fixed submission:
A,B=map(int,input().split())
if A<=5:
  print(0)
elif 6<=A<=12:
  print(int(B/2))
elif A>=13:
  print(B)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
data=[[int(x) for x in input().split()] for m in range(M)]
_min=min([m[0] for m in data])
_max=max([m[1] for m in data])
data=[list(range(m[0],m[1]+1)) for m in data]
#print(data)
count=0
for i in range(_min,_max+1):
    count+=(sum([(i in m) for m in data])==len(data))
print(count)


Fixed submission:
N,M=map(int,input().split())
data=[[int(x) for x in input().split()] for m in range(M)]
_min=max([m[0] for m in data])
_max=min([m[1] for m in data])
a=_max-_min+1
print(a if a>=0 else 0)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
S=input()
for i,m in enumerate(S):
    if m=="A":
        S[i]="A"
    if m=="B":
        S[i]="B"
    if m=="C":
        S[i]="C"
print(S)


Fixed submission:
N,K=map(int,input().split())
S=input()
SS=""
for i,s in enumerate(S):
    if i==K-1:
        if s=="A":
            s="a"
        if s=="B":
            s="b"
        if s=="C":
            s="c"
    SS+=s
print(SS)

Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
S=input()
for i,m in enumerate(S):
    if m=="A":
        S[i]="A"
    if m=="B":
        S[i]="B"
    if m=="C"
        S[i]="C"
print(S)


Fixed submission:
N,K=map(int,input().split())
S=input()
SS=""
for i,s in enumerate(S):
    if i==K-1:
        if s=="A":
            s="a"
        if s=="B":
            s="b"
        if s=="C":
            s="c"
    SS+=s
print(SS)
Buggy python submission (verdict: Runtime Error):
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=ittenai.pop(x)
    stack=deque([x])

    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)


Fixed submission:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=ittenai.pop()
    stack=deque([x])

    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=list(ittenai)[0]
    stack=deque([x])
    ittenai.remove(x)
    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)


Fixed submission:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=ittenai.pop()
    stack=deque([x])

    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)
Buggy python submission (verdict: Runtime Error):
N=int(input())
value=0
if N==1:
    print(A)
    exit()
if N==2:
    print(0)
    exit()
for i in range(1,int(N**.5+10)):
    if N%i==0 and N//i>=i+1:
        value+=N//i-1
print(value)


Fixed submission:
N=int(input())
value=0
if N==1:
    print(0)
    exit()
if N==2:
    print(0)
    exit()
for i in range(1,int(N**.5+10)):
    if N%i==0 and N//i>=i+2:
        value+=N//i-1
print(value)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
flag=(S[0]=="#")
count=0
for i in range(1,len(S)):
    if not flag:
        flag=(S[i]=="#" and S[i-1]==".")
    if flag:
        if S[i]=="." and S[i-1]=="#":
            count+=1
            s[i]="#"
print(count)

Fixed submission:
N=int(input())
S=input()
use=[0 if S[i]=="." else 1 for i in range(N)]
now=[0 for i in range(N)]
count=sum(use)
lst=set()
lst.add(count)


for i in range(N-1,-1,-1):
    now[i]=1
    if use[i]:
        use[i]=0
        count-=1
    else:
        use[i]=1
        count+=1
    lst.add(count)
print(min(lst))
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
S=input()
if N==1:
    print(1)
    exit()

lst0=[]

lst1=[]
if S[0]!="1":
    lst1.append([0,0])
flag=0
for i in range(N):
    if flag==0 and S[i]=="1":
        flag=1
        st=i
    elif flag and S[i]=="0":
        lst1.append([st,i-1])
        flag=0
if S[-1]!="1":
    lst1.append([N-1,N-1])

if flag:
    lst1.append([st,N-1])
flag=0
for i in range(N):
    if flag==0 and S[i]=="0":
        flag=1
        st=i
    elif flag and S[i]=="1":
        lst0.append([st,i-1])
        flag=0
if flag:
    lst0.append([st,N-1])

if K>=len(lst1):
    print(N)
else:
    value=0
    for i in range(len(lst1)-K):
        a=lst1[i+K][1]-lst1[i][0] +1
        if a>value:
            value=a
print(value)


Fixed submission:
N,K=map(int,input().split())
S=input()
if N==1:
    print(1)
    exit()


lst=[]
if S[0]!="1":
    lst.append([0,0])
flag=0
for i in range(N):
    if flag==0 and S[i]=="1":
        flag=1
        st=i
    elif flag and S[i]=="0":
        lst.append([st,i-1])
        flag=0
if S[-1]!="1":
    lst.append([N-1,N-1])

if flag:
    lst.append([st,N-1])

if K>=len(lst):
    print(N)
    exit()
else:
    value=0
    for i in range(len(lst)-K):
        a=lst[i+K][1]-lst[i][0] +1
        if a>value:
            value=a
print(value)
Buggy python submission (verdict: Time Limit Exceeded):
#print("UNKO"[2:3])

N,Q=map(int,input().split())
S=input()
LR=[[list(map(int,input().split())),i,0] for i in range(Q)]
LR=sorted(LR,key=lambda x: x[0][1])
#print(LR)
minl=min([i[0][0] for i in LR])
maxr=max([i[0][1] for i in LR])
Qidx=0
for i in range(minl-1,maxr-1):
    #print(i,Qidx, S[i]+S[i+1])
    if S[i]+S[i+1]=="AC":
        for q in range(Qidx,Q):
            if i+1>LR[q][0][1]-1:
                Qidx=q+1
                continue
            if i<LR[q][0][0]-1:
                continue

            LR[q][2]+=1

LR=sorted(LR,key=lambda x: x[1])
for i in LR:
    print(i[2])


Fixed submission:
N,Q=map(int,input().split())
S=input()
LR=[map(int,input().split()) for i in range(Q)]

data=[0 for i in range(N)]
for i in range(N-1):
    data[i+1]=data[i]
    if S[i]+S[i+1]=="AC":
        data[i+1]+=1
for l,r in LR:
    print(data[r-1]-data[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
#print("UNKO"[2:3])

N,Q=map(int,input().split())
S=input()
LR=[[list(map(int,input().split())),i,0] for i in range(Q)]
LR=sorted(LR,key=lambda x: x[0][0])
minl=min([i[0][0] for i in LR])
maxr=max([i[0][1] for i in LR])
Qidx=0
for i in range(minl-1,maxr-1):
    if S[i]+S[i+1]=="AC":
        for q in range(Qidx,Q):
            if i<LR[q][0][0]-1:
                break
            if i+1>LR[q][0][1]-1:
                continue
            LR[q][2]+=1

LR=sorted(LR,key=lambda x: x[1])
for i in LR:
    print(i[2])


Fixed submission:
N,Q=map(int,input().split())
S=input()
LR=[map(int,input().split()) for i in range(Q)]

data=[0 for i in range(N)]
for i in range(N-1):
    data[i+1]=data[i]
    if S[i]+S[i+1]=="AC":
        data[i+1]+=1
for l,r in LR:
    print(data[r-1]-data[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for i in range(Q)]
for l,r in LR:
    count=0
    for i in range(l-1,r-1):
        count+= S[i]+S[i+1]=="AC"
    print(count)


Fixed submission:
N,Q=map(int,input().split())
S=input()
LR=[map(int,input().split()) for i in range(Q)]

data=[0 for i in range(N)]
for i in range(N-1):
    data[i+1]=data[i]
    if S[i]+S[i+1]=="AC":
        data[i+1]+=1
for l,r in LR:
    print(data[r-1]-data[l-1])