Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
mat = [input() for i in range(W)]
mat_t = [''.join(x) for x in zip(*mat)]
def check(mat, t):
    stack = set()
    for i, string in enumerate(mat):
        string = '.' + string + '.'
        for j in range(len(string)):
            if j+3<=len(string):
                if string[j:j+3] == '.#.':
                    if t==False:
                        stack.add((i, j))
                    else:
                        stack.add((j, i))
    return stack

stack1 = check(mat, False)
stack2 = check(mat_t, True)
if stack1 & stack2:
    print('No')
else:
    print('Yes')

Fixed submission:
H, W = map(int, input().split())
mat = [input() for i in range(H)]
mat_t = [''.join(x) for x in zip(*mat)]
def check(mat, t):
    stack = set()
    for i, string in enumerate(mat):
        string = '.' + string + '.'
        for j in range(len(string)):
            if j+3<=len(string):
                if string[j:j+3] == '.#.':
                    if t==False:
                        stack.add((i, j))
                    else:
                        stack.add((j, i))
    return stack

stack1 = check(mat, False)
stack2 = check(mat_t, True)
if stack1 & stack2:
    print('No')
else:
    print('Yes')

Buggy python submission (verdict: Runtime Error):
%%test_input https://atcoder.jp/contests/abc096/tasks/abc096_c
# 巡回セールスマン問題？
H, W = map(int, input().split())
mat = [input() for i in range(W)]
mat_t = [''.join(x) for x in zip(*mat)]
def check(mat, t):
    stack = set()
    for i, string in enumerate(mat):
        string = '.' + string + '.'
        for j in range(len(string)):
            if j+3<=len(string):
                if string[j:j+3] == '.#.':
                    if t==False:
                        stack.add((i, j))
                    else:
                        stack.add((j, i))
    return stack

stack1 = check(mat, False)
stack2 = check(mat_t, True)
if stack1 & stack2:
    print('No')
else:
    print('Yes')

Fixed submission:
H, W = map(int, input().split())
mat = [input() for i in range(H)]
mat_t = [''.join(x) for x in zip(*mat)]
def check(mat, t):
    stack = set()
    for i, string in enumerate(mat):
        string = '.' + string + '.'
        for j in range(len(string)):
            if j+3<=len(string):
                if string[j:j+3] == '.#.':
                    if t==False:
                        stack.add((i, j))
                    else:
                        stack.add((j, i))
    return stack

stack1 = check(mat, False)
stack2 = check(mat_t, True)
if stack1 & stack2:
    print('No')
else:
    print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = list(map(int, input().split()))
X_sort = sorted(X)
for i in range(N):
    x = X[i]
    index = X_sort.index(x)
    if index<= int(N//2-1):
        print(X_sort[N//2])
    else:
        print(X_sort[N//2-1])

Fixed submission:
N = int(input())
X = list(map(int, input().split()))
X_sort = sorted(X)
m_1 = X_sort[N//2]
m_2 = X_sort[N//2-1]
for i in range(N):
    x = X[i]
    if x<= m_2:
        print(m_1)
    else:
        print(m_2)
Buggy python submission (verdict: Runtime Error):
A, B, C, D, E, F = map(int, input().split())
waters = set()
sugars = set()
for i in range(F//(A*100)+1):
    for j in range(F//(B*100)+1):
        if i!=0 or j!=0:
            if A*i +B*j <= F:
                waters.add(100*A*i+100*B*j)
for i in range(F//(C)+1):
    for j in range(F//(D)+1):
        if C*i +D*j <= F:
            sugars.add(C*i+D*j)

max_ratio = 0
for water in waters:
    for sugar in sugars:
        ratio =  sugar/(water+sugar)
        if water+sugar<=F and sugar<=E*(water//100):
            if ratio > max_ratio:
                ans = (water+sugar, sugar)
                max_ratio = ratio
print(*ans)

Fixed submission:
A, B, C, D, E, F = map(int, input().split())
waters = set()
sugars = set()
for i in range(F//(A*100)+1):
    for j in range(F//(B*100)+1):
        if i!=0 or j!=0:
            if A*i*100 +B*j*100 <= F:
                waters.add(100*A*i+100*B*j)
for i in range(F//(C)+1):
    for j in range(F//(D)+1):
        if C*i +D*j <= F:
            sugars.add(C*i+D*j)

max_ratio = 0
for water in waters:
    for sugar in sugars:
        ratio =  sugar/(water+sugar)
        if water+sugar<=F and sugar<=E*(water//100):
            if ratio >= max_ratio:
                ans = (water+sugar, sugar)
                max_ratio = ratio
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
ans = 0
for num in range(min(A), max(A)+1):
    tmp = [1 if abs(a-num)<=1 else 0 for a in A]
    ans = max(ans, sum(tmp))
print(ans)

Fixed submission:
n = int(input())
A = sorted(list(map(int, input().split())))
count = dict()
for a in A:
    for i in range(a-1, a+2):
        if i not in count:
            count[i] = 1
        else:
            count[i] += 1
print(max(count.values()))
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
# 2本以上ある棒, 4本以上を選び出してsort, 大きいものから選ぶ
A = sorted(A)
c = collections.Counter(A)
c_2 = sorted(c.items(), key=lambda x:x[0], reverse=True)
count = 0
for i in range(n):
    if c_2[i][1] >=4 and count==0:
        ans = c_2[i][0] **2
        count+=2
        break
    elif c_2[i][1]>=2:
        if count==0:
            ans = c_2[i][0]
            count+=1
        elif count==1:
            ans *= c_2[i][0]
            count+=1
            break
if count!=2:
    print(0)
else:
    print(ans)

Fixed submission:
import collections
n = int(input())
A = list(map(int, input().split()))
# 2本以上ある棒, 4本以上を選び出してsort, 大きいものから選ぶ
A = sorted(A)
c = collections.Counter(A)
c_2 = sorted(c.items(), key=lambda x:x[0], reverse=True)
count = 0
for i in range(n):
    if c_2[i][1] >=4 and count==0:
        ans = c_2[i][0] **2
        count+=2
        break
    elif c_2[i][1]>=2:
        if count==0:
            ans = c_2[i][0]
            count+=1
        elif count==1:
            ans *= c_2[i][0]
            count+=1
            break
if count!=2:
    print(0)
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=list(input())

minimum=N
for i in range (N+1):
  white=S[:i].count("#")
  black=S[i:].count(".")
  minimum=min(minimum, white+black)
print(minimum)


Fixed submission:
N=int(input())
S=input()

white=S.count(".")
countb=0
ans=white

for i in range (len(S)):
  if S[i]==".":
    white -=1
  else:
    countb +=1 
  ans=min(ans, countb+white)

print(ans)

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

count=S.count(".")
first=S.index("#")

print(count-first) if "#" in S else print(N)

Fixed submission:
N=int(input())
S=input()

white=S.count(".")
countb=0
ans=white

for i in range (len(S)):
  if S[i]==".":
    white -=1
  else:
    countb +=1 
  ans=min(ans, countb+white)

print(ans)
Buggy python submission (verdict: Runtime Error):
S = []
for _ in range(5):
    S.append(int(input()))

q=[] #quotient
r=[] #reminder
count0=0 #余りが0の時を検出
for i in S:
  j, k= divmod(i, 10)
  q.append(j)
  if k==0:
    count0+=1
  else:
    r.append(k)

# sum(q)*10→商をベースに基本値を算出
# 10*(4-count0)→余り分の待ち時間を算出。ただし、余り0の場合には待ち時間なし
# min(r)→最も余りが短い料理を最後に注文する
print(sum(q)*10+10*(4-count0)+min(r))
  

Fixed submission:
S = []
for _ in range(5):
    S.append(int(input()))

q=[] #quotient
r=[] #reminder
count0=0 #余りが0の時を検出
for i in S:
  j, k= divmod(i, 10)
  q.append(j)
  if k==0:
    count0+=1
  else:
    r.append(k)

# sum(q)*10→商をベースに基本値を算出
# 10*(4-count0)→余り分の待ち時間を算出。ただし、余り0の場合には待ち時間なし
# min(r)→最も余りが短い料理を最後に注文する
# 最初、すべてが0になる場合を想定できていなかったので、REになった
if count0==5:
  print(sum(S))
else:
  print(sum(q)*10+10*(4-count0)+min(r))
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())
  SP= S[l-1:r]
  print(SP.count("AC"))


Fixed submission:
N, Q = map(int, input().split())
S= input()

count=[]
ans=0
for i in range (N):
  if i!=0 and S[i-1]=="A" and S[i]=="C":
    ans+=1
    count.append(ans)
  else:
    count.append(ans)
#print(count)

for _ in range(Q):
  l, r=map(int, input().split())
  print(count[r-1]-count[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
A, B, C = list(map(int, input().split()))

count=0
for i in range (A, B+1):
  if i % C ==0.:
    count +=1
print (count)

Fixed submission:
a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
Buggy python submission (verdict: Runtime Error):
#人の回答を写経したもの
dic = {k: list(input()) for k in "abc"}

while dic[s]:
  s=dic[s].pop(0)

print(s.upper())

Fixed submission:

#他人の答えの写経
dic = {k: list(input()) for k in "abc"}

s ="a"

while dic[s]:
  s=dic[s].pop(0)

print(s.upper())
Buggy python submission (verdict: Runtime Error):
length=list(map(int, input().split()))
lenght.sort()
print ("Yes" if length==[5,5,7] else "No")

Fixed submission:
abc = list(map(int, input().split()))
abc.sort()
print('YES' if [5, 5, 7]==abc else 'NO')
Buggy python submission (verdict: Runtime Error):
import math
 
n = int(input())
li = list(map(int,input().split()))
 
leftgcd = [0 for i in range(n)]
rightgcd = [0 for i in range(n)]
 
leftgcd[0] = li[0]
rightgcd[n - 1] = li[n - 1]
 
if n == 2:
  print(max(li[0], li[1]))
else:
  for j in range(1, n):
    leftgcd[j] = math.gcd(li[j], leftgcd[j - 1])
    rightgcd[n - 1 - j] = math.gcd(li[n - 1 - j], rightgcd[n - j])

  ans = max(leftgcd[n - 2], rightgcd[1])
  for k in range(1, n - 1):
    g = math.gcd(leftgcd[k - 1], rightgcd[k + 1])
    if g > ans:
      ans = g
  print(ans)

Fixed submission:
import fractions
 
n = int(input())
li = list(map(int,input().split()))
 
leftgcd = [0 for i in range(n)]
rightgcd = [0 for i in range(n)]
 
leftgcd[0] = li[0]
rightgcd[n - 1] = li[n - 1]
 
if n == 2:
  print(max(li[0], li[1]))
else:
  for j in range(1, n):
    leftgcd[j] = fractions.gcd(li[j], leftgcd[j - 1])
    rightgcd[n - 1 - j] = fractions.gcd(li[n - 1 - j], rightgcd[n - j])
 
  ans = max(leftgcd[n - 2], rightgcd[1])
  for k in range(1, n - 1):
    g = fractions.gcd(leftgcd[k - 1], rightgcd[k + 1])
    if g > ans:
      ans = g
  print(ans)

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

n = int(input())
li = list(map(int,input().split()))

leftgcd = [0 for i in range(n)]
rightgcd = [0 for i in range(n)]

leftgcd[0] = li[0]
rightgcd[n - 1] = li[n - 1]

for j in range(1, n):
  leftgcd[j] = math.gcd(li[j], leftgcd[j - 1])
  rightgcd[n - 1 - j] = math.gcd(li[n - 1 - j], rightgcd[n - j])
  
ans = max(leftgcd[n - 2], rightgcd[1])
for k in range(1, n - 1):
  g = math.gcd(leftgcd[k - 1], rightgcd[k + 1])
  if g > ans:
    ans = g
print(ans)

Fixed submission:
import fractions
 
n = int(input())
li = list(map(int,input().split()))
 
leftgcd = [0 for i in range(n)]
rightgcd = [0 for i in range(n)]
 
leftgcd[0] = li[0]
rightgcd[n - 1] = li[n - 1]
 
if n == 2:
  print(max(li[0], li[1]))
else:
  for j in range(1, n):
    leftgcd[j] = fractions.gcd(li[j], leftgcd[j - 1])
    rightgcd[n - 1 - j] = fractions.gcd(li[n - 1 - j], rightgcd[n - j])
 
  ans = max(leftgcd[n - 2], rightgcd[1])
  for k in range(1, n - 1):
    g = fractions.gcd(leftgcd[k - 1], rightgcd[k + 1])
    if g > ans:
      ans = g
  print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
li = []
for i in range(5):
  li.append(int(input())
m = min(li)
t = int(n / m)
print(t + 5)

Fixed submission:
n = int(input())
li = []
for i in range(5):
  li.append(int(input()))
m = min(li)
if n % m != 0:
	t = n // m
else:
  t = n // m - 1
print(t + 5)
Buggy python submission (verdict: Runtime Error):
n, q = map(int,input().split())
s = input()
inputlist = []
for i in range(q):
  inputlist.append(list(map(int,input().split())))

aclist = []
acnum = 0
for j in range(n - 1):
  if s[j] == "A" and s[j + 1] == "C":
    aclist.append(j)
    acnum += 1
rightac = []
acindex = 0
for j2 in range(n):
  if j2 == aclist[acindex] + 1:
    acindex = min(acindex + 1, len(aclist) - 1)
    acnum -= 1
  rightac.append(acnum)

anslist = []
for k in range(q):
  ans = rightac[inputlist[k][0] - 1] - rightac[inputlist[k][1] - 1]
  anslist.append(ans)

print(*anslist, sep = "\n")

Fixed submission:
n, q = map(int,input().split())
s = input()
inputlist = []
for i in range(q):
  inputlist.append(list(map(int,input().split())))

aclist = []
acnum = 0
for j in range(n - 1):
  if s[j] == "A" and s[j + 1] == "C":
    aclist.append(j)
    acnum += 1
if acnum == 0:
  for i in range(q):
    print(0)
else:
  rightac = []
  acindex = 0
  for j2 in range(n):
    if j2 == aclist[acindex] + 1:
      acindex = min(acindex + 1, len(aclist) - 1)
      acnum -= 1
    rightac.append(acnum)

  anslist = []
  for k in range(q):
    ans = rightac[inputlist[k][0] - 1] - rightac[inputlist[k][1] - 1]
    anslist.append(ans)

  print(*anslist, sep = "\n")
Buggy python submission (verdict: Runtime Error):
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"

for c1 in s:
  for c2 in s:
    for c3 in s:
      dp[0][c1 + c2 + c3] = 0

dp[0]["TTT"] = 1

for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[j + 1][c2 + c3 + p] += dp[j][c1 + c2 + c3]

ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
print(ans)

Fixed submission:
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7
 
for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][c1 + c2 + c3] = 0
 
dp[0]["TTT"] = 1
 
for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[l + 1][c2 + c3 + p] += dp[l][c1 + c2 + c3]
          dp[l + 1][c2 + c3 + p] = dp[l + 1][c2 + c3 + p] % M
 
ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
drink = []
for i in range(n):
  drink.append(list(map(int,input().split())))
sorteddrink = sorted(drink, key = lambda x:x[0])

count = 0
cost = 0
index = 0

while True:
  if index > n - 1:
    break
  if count + sorteddrink[index][1] > m:
    break
  cost += sorteddrink[index][0] * sorteddrink[index][1]
  count += sorteddrink[index][1]
  index += 1

cost += sorteddrink[index][0] * (m - count)
print(cost)

Fixed submission:
n, m = map(int,input().split())
drink = []
for i in range(n):
  drink.append(list(map(int,input().split())))
sorteddrink = sorted(drink, key = lambda x:x[0])

count = 0
cost = 0
index = 0

while True:
  if index > n - 1:
    break
  if count + sorteddrink[index][1] > m:
    break
  cost += sorteddrink[index][0] * sorteddrink[index][1]
  count += sorteddrink[index][1]
  index += 1

if index <= n - 1:
  cost += sorteddrink[index][0] * (m - count)
print(cost)

Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
drink = []
for i in range(n):
  drink.append(list(map(int,input().split())))
sorteddrink = sorted(drink, key = lambda x:x[0])

count = 0
cost = 0
index = 0

while True:
  if count + sorteddrink[index][1] > m:
    break
  cost += sorteddrink[index][0] * sorteddrink[index][1]
  count += sorteddrink[index][1]
  index += 1
  
cost += sorteddrink[index][0] * (m - count)
print(cost)

Fixed submission:
n, m = map(int,input().split())
drink = []
for i in range(n):
  drink.append(list(map(int,input().split())))
sorteddrink = sorted(drink, key = lambda x:x[0])

count = 0
cost = 0
index = 0

while True:
  if index > n - 1:
    break
  if count + sorteddrink[index][1] > m:
    break
  cost += sorteddrink[index][0] * sorteddrink[index][1]
  count += sorteddrink[index][1]
  index += 1

if index <= n - 1:
  cost += sorteddrink[index][0] * (m - count)
print(cost)
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

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

    def sizeCheck(self, x):
        x = self.find(x)
        return self.size[x]

    def sameCheck(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
n, m = map(int, input().split())
bridge = []
for i in range(m):
  bridge.append(list(map(int, input().split())))
ans = [int(n * (n - 1) / 2)]

uf = UnionFind(n)
index = m - 1
while index > 0:
  li = bridge[index]
  if uf.sameCheck(li[0], li[1]):
    ans = [ans[0]] + ans
    index -= 1
  else:
    s0 = uf.sizeCheck(li[0])
    s1 = uf.sizeCheck(li[1])
    uf.union(li[0], li[1])
    ans = [ans[0] - s0 * s1] + ans
    index -= 1
print(*ans, sep = "\n")
  

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

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

    def sizeCheck(self, x):
        x = self.find(x)
        return self.size[x]

    def sameCheck(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n, m = map(int, input().split())
bridge = []
for i in range(m):
  bridge.append(list(map(int, input().split())))
ans = [0] * m
ans[m - 1] = int(n * (n - 1) / 2)

uf = UnionFind(n)
index = m - 1
while index > 0:
  li = bridge[index]
  if uf.sameCheck(li[0], li[1]):
    ans[index - 1] = ans[index]
    index -= 1
  else:
    s0 = uf.sizeCheck(li[0])
    s1 = uf.sizeCheck(li[1])
    uf.union(li[0], li[1])
    ans[index - 1] = ans[index] - s0 * s1
    index -= 1
print(*ans, sep = "\n")
Buggy python submission (verdict: Runtime Error):
n = int(input())
money = []
tuka = []
for i in range(n):
  li = input().split()
  money.append(int(li[0]))
  tuka.append(li[1])
  
ans = 0
for j in range(n):
  if tuka[j] == "JPY":
    ans += money[j]
  else:
    ans += 380000 * money[j]
print(ans)

Fixed submission:
n = int(input())
money = []
tuka = []
for i in range(n):
    li = input().split()
    money.append(float(li[0]))
    tuka.append(li[1])

ans = 0
for j in range(n):
    if tuka[j] == "JPY":
        ans += money[j]
    else:
        ans += 380000 * money[j]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a, b):
  while a:
    a, b = b % a, a
  return b

from functools import reduce

def g():
  n = int(input())
  vs = list(map(int, input().split()))
  
  mr = 0
  for i in range(len(vs)):
    r = reduce(gcd, vs[:i]+vs[i+1:])
    mr = max(mr, r)
  return mr
  
print(g())


Fixed submission:
def gcd(a, b):
  while a:
    a, b = b % a, a
  return b


def g():
  from functools import reduce
  n = int(input())
  vs = list(map(int, input().split()))
  
  while True:
    n = len(vs)
    
    if n < 10:
      mrr = 0
      for i, v in enumerate(vs):
        rr = reduce(gcd, vs[:i]+vs[i+1:])
        mrr = max(rr, mrr)
      return mrr
    
    v1 = vs[:n//2]
    v2 = vs[n//2:]
    
    r1 = reduce(gcd, v1)
    r2 = reduce(gcd, v2)
    if r1 == r2:
      return r1
    if r1 > r2:
      vs = v2
    else:
      vs = v1
  
  
print(g())
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s = input()

from itertools import groupby

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
aaa = list(gen(s))
r = 2 * k + 1
if len(aaa) <= r:
  mc = sum(aaa)
else:
  for i in range(0, len(aaa) - r + 1 , 2):
    mc = max(mc, sum(aaa[i:i+r]))
print(mc)
  
    

Fixed submission:
n, k = map(int, input().split())
s = input()

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s = input()

ss = []
tt = []

if s[0] == '0':
  tt += [0]

c = 1
for i in range(1, n):
  if s[i-1:i+1] == '00':
    c += 1
  if s[i-1:i+1] == '10':
    tt += [c]
    c = 1
  if s[i-1:i+1] == '11':
    c += 1
  if s[i-1:i+1] == '01':
    ss += [c]
    c = 1
if s[n-1] == '0':
  ss += [c]
else:
  tt += [c]

sr = k
tr = k + 1

sl = len(ss)
tl = len(tt)

mm = 0
for i in range(tl):
  try:
    m = sum(ss[i:i+sr]) + sum(tt[i:i+tr])
    if mm < m:
      mm = m
  except:
    pass
print(mm)


Fixed submission:
n, k = map(int, input().split())
s = input()

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
t = ''

if s[0] == '0':
  t += '0'
c = 1
for i in range(1, n):
  if s[i-1] == '0' and s[i] == '0':
    c += 1
  if s[i-1] == '1' and s[i] == '0':
    t += str(c)
    c = 1
  if s[i-1] == '0' and s[i] == '1':
    t += str(c)
    c = 1
  if s[i-1] == '1' and s[i] == '1':
    c += 1
t += str(c)
t = list(map(int, t))
print(t)

# 範囲
r = 2 * k + 1
gs = []
for i in range(0,n,2):
  if i + r < n:
    gs.append(sum(t[i:i+r]))
print(max(gs))


Fixed submission:
n, k = map(int, input().split())
s = input()

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
s = input()
rr = (list(map(int, input().split())) for _ in range(k))

from collections import Counter

for a, b in rr:
  c = Counter(s[a-1:b].replace('AC', '1'))['1']
  print(c)


Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
s = input()
rr = (list(map(int, input().split())) for _ in range(k))

from collections import Counter

dc = [0, 0]
c = 0
for i in range(1, len(s)):
  if s[i-1]+s[i] == 'AC':
    c += 1
  dc.append(c)
for a, b in rr:
  print(dc[b] - dc[a])