Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

s = input()
q = int(input())
qs = [list(input().split()) for i in range(q)]

q1_cnt = 0
for qi in qs:
    if qi[0]=="1":
        q1_cnt+=1
    else:
        if q1_cnt%2==0:
            if qi[1]=="1":
                s = qi[2]+s
            else:
                s = s+qi[2]
        else:
            if qi[1]=="1":
                s = s+qi[2]
            else:
                s = qi[2]+s

if q1_cnt%2==1:
    s = s[::-1]
print(s)

Fixed submission:
# -*- coding: utf-8 -*-

s = input()
q = int(input())
qs = [list(input().split()) for i in range(q)]

pls_vec = []
pls_append = pls_vec.append

mns_vec = []
mns_append = mns_vec.append

q1_vec = 1
for qi in qs:
    if qi[0]=="1":
        q1_vec*=(-1)
    else:
        if q1_vec==1:
            if qi[1]=="1":
                mns_append(qi[2])
            else:
                pls_append(qi[2])
        else:
            if qi[1]=="1":
                pls_append(qi[2])
            else:
                mns_append(qi[2])

ret = "".join(mns_vec[::-1]) + s + "".join(pls_vec)
if q1_vec==-1:
    ret=ret[::-1]
print(ret)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
a,b,c = list(map(int,input().split()))
ret = "No"
if len(set(a,b,c))==2:
    ret = "Yes"
print(ret)


Fixed submission:
# -*- coding: utf-8 -*-
a,b,c = list(map(int,input().split()))
ret = "No"
if len(set([a,b,c]))==2:
    ret = "Yes"
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
h,n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
a = [i[0] for i in ab]
b = [i[1] for i in ab]

from math import ceil
dp = [[0] * (h + 1) for _ in range(n)]

for j in range(h+1):
    dp[0][j] = ceil(j/a[0]) * b[0]

for i in range(1,n):
    for j in range(h+1):
        if j - a[i] > 0:
            dp[i][j] = min(dp[i][j-a[i]] + b[i],dp[i-1][j])
        else:
            dp[i][j] = min(b[i],dp[i-1][j])

print(dp[n-1][h])

Fixed submission:
# -*- coding: utf-8 -*-
h,n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
a = [i[0] for i in ab]
b = [i[1] for i in ab]
 
from math import ceil
dp = [[0] * (h + 1) for _ in range(n)]
 
for j in range(h+1):
    dp[0][j] = ceil(j/a[0]) * b[0]
 
for i in range(1,n):
    for j in range(h+1):
        if j - a[i] > 0:
            dp[i][j] = min(dp[i][j-a[i]] + b[i],dp[i-1][j])
        else:
            dp[i][j] = min(b[i],dp[i-1][j])
 
print(dp[n-1][h])
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
abi = [[] for _ in range(n+1)]
ans = [0] * (n-1)
for i,(a,b) in enumerate(ab):
    abi[a].append((i,b))
    abi[b].append((i,a))

def dfs(v,parent=-1,color=-1):
    k=1
    for i in abi[v]:
        if parent==i[1]:continue
        if(k==color):k+=1
        ans[i[0]]=k
        k+=1
        dfs(i[1],v,ans[i[0]])

dfs(1)

print(max(ans))
for i in ans:
    print(i)

Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
ans = [0] * (n-1)
abi = [[] for _ in range(n+1)]
#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)
for i,(a,b) in enumerate(ab):
    abi[a].append((i,b))
    abi[b].append((i,a))

def dfs(v,parent=-1,color=-1):
    k=1
    for i in abi[v]:
        if parent==i[1]:continue
        if(k==color):k+=1
        ans[i[0]]=k
        k+=1
        dfs(i[1],v,ans[i[0]])

dfs(1)

print(max(ans))
for i in ans:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
s = input()


inf=float("inf")
#i番目のマスに行くための最小手数と、その出目
from copy import copy
dp = [(0,[])] + [(inf,None) for _ in range(n)]
for i in range(1,n+1):
    if s[i]=="0":
        for j in range(m,0,-1):
            if i-j<0:
                continue
            if dp[i-j][0]<inf:
                dp[i]=(dp[i-j][0]+1,dp[i-j][1]+[j])
                break
if dp[-1][1]:

    print(" ".join(map(str,dp[-1][1])))
else:
    print(-1)

Fixed submission:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
s = input()


inf=float("inf")
#i番目のマスに行くための最小手数と、なんマス移動してきたか
dp = [(0,0)] + [(inf,None) for _ in range(n)]
for i in range(1,n+1):
    if s[i]=="0":
        for j in range(min(m,i),0,-1):
            if dp[i-j][0]<inf:
                dp[i]=(dp[i-j][0]+1,j)
                break
if dp[-1][1]:
    i = n
    ret = []
    ra = ret.append
    while dp[i][1]:
        ra(dp[i][1])
        i-=dp[i][1]
    print(" ".join(map(str,ret[::-1])))
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
a,b = list(map(int,input().split()))
#最大公約数
import fractions
_gcd = fractions.gcd(a, b)

if _gcd == 1:
    print(1)
    import sys
    sys.exit()

def primes(n):
    #2~nまでの素数を列挙
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
pms = primes(_gcd) #sqrt(_gcd) までの素数を列挙
ret = 1
for i in pms:
    if _gcd%i==0:
        ret+=1
print(ret)

Fixed submission:
# -*- coding: utf-8 -*-
a,b = list(map(int,input().split()))
#最大公約数

#最大公約数
import fractions
abgcd = fractions.gcd(a, b)

def prime_factorize(N):
    #素因数分解
    from collections import defaultdict
    factorize = defaultdict(int)
    while N%2 == 0:
        factorize[2]+=1
        N //= 2
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        while N%i == 0:
            factorize[i] += 1
            N //= i
    if N!=1:factorize[N]=1
    return factorize

print(len(prime_factorize(abgcd).keys())+1)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
a,b = list(map(int,input().split()))
#最大公約数
import fractions
_gcd = fractions.gcd(a, b)

def primes(n):
    #2~nまでの素数を列挙
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
pms = primes(_gcd) #sqrt(_gcd) までの素数を列挙
ret = 1
for i in pms:
    if _gcd%i==0:
        ret+=1
print(ret)

Fixed submission:
# -*- coding: utf-8 -*-
a,b = list(map(int,input().split()))
#最大公約数

#最大公約数
import fractions
abgcd = fractions.gcd(a, b)

def prime_factorize(N):
    #素因数分解
    from collections import defaultdict
    factorize = defaultdict(int)
    while N%2 == 0:
        factorize[2]+=1
        N //= 2
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        while N%i == 0:
            factorize[i] += 1
            N //= i
    if N!=1:factorize[N]=1
    return factorize

print(len(prime_factorize(abgcd).keys())+1)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
price = [0] * m
can_opens = [0] * m
for i in range(m):
    a,b = list(map(int,input().split()))
    price[i]=a
    c = ["0"] * n
    ci = list(map(int,input().split()))
    for j in ci:
        c[n- j]="1"
    can_opens[i]=int("".join(c),2)
inf=float("inf")
dp = [inf] * 2**n
dp[0]=0
#dp[i]は、iを取るために必要な最小費用
for i,(pi,coi) in enumerate(zip(price,can_opens)):
    for j in range(2**n):
        dp[j|coi]=min(dp[j|coi],dp[j]+pi)
from math import isinf
if isinf(dp[-1]):
    print(-1)
else:
    print(dp[-1])

Fixed submission:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
price = [0] * m
can_opens = [0] * m
for i in range(m):
    a,b = list(map(int,input().split()))
    price[i]=a
    c = ["0"] * n
    ci = list(map(int,input().split()))
    for j in ci:
        c[n- j]="1"
    can_opens[i]=int("".join(c),2)
inf=float("inf")
dp = [inf] * 2**n
dp[0]=0
#dp[i]は、iを取るために必要な最小費用
for i,(pi,coi) in enumerate(zip(price,can_opens)):
    for j in range(2**n):
        dp[j|coi]=min(dp[j|coi],dp[j]+pi)
from math import isinf
if isinf(dp[-1]):
    print(-1)
else:
    print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
from decimal import Decimal

n,m = list(map(int,input().split()))
a = list(map(lambda x : Decimal(int(x) * (-1)) ,input().split()))

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = heappop(a)/2
    heappush(a,tmp_min)

print(sum(list(map(lambda x : int(x * (-1)),a))))

Fixed submission:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n,m = list(map(int,input().split()))
a = list(map(lambda x : int(x) * (-1) ,input().split()))

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = (-1)*heappop(a)//2*(-1)
    heappush(a,tmp_min)

print(sum(list(map(lambda x : int(x * (-1)),a))))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
from decimal import Decimal

n,m = list(map(int,input().split()))
a = list(map(int,input().split()))

trans = lambda x : Decimal(x) * (-1)

a = list(map(trans,a))

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    j = heappop(a)/2
    heappush(a,j)

print(sum(list(map(lambda x:int(x*-1),a))))

Fixed submission:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n,m = list(map(int,input().split()))
a = list(map(lambda x : int(x) * (-1) ,input().split()))

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = (-1)*heappop(a)//2*(-1)
    heappush(a,tmp_min)

print(sum(list(map(lambda x : int(x * (-1)),a))))
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[b-1].append(a-1)
        edges[a-1].append(b-1)

    counts = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        counts[p-1] += x

    parent_nodes = deque()
    parent_nodes.append(0)
    visited_nodes = set()
    while parent_nodes:
        parent = parent_nodes.popleft()
        if parent in visited_nodes:
            continue
        visited_nodes.add(parent)
        for child in edges[parent]:
            if child in visited_nodes:
                continue
            counts[child] += counts[parent]
            parent_nodes.append(child)

    print(' '.join(list(map(str, counts))))

if __name__ == "__main__":
    main()

Fixed submission:
# -*- coding: utf-8 -*-
a = int(input())
s = input()
if a >= 3200:
    print(s)
else:
    print("red")
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
d = [list(map(int,input().split())) for i in range(n)]
d.sort(key = lambda x:x[0])
d.sort(key = lambda x:x[1],reverse=True)

from heapq import heappush, heappop
hq = []
for i,ab in enumerate(d):
    heappush(hq,(i,ab))

cur_dat = 1
ret = 0
while cur_dat <= m:
    val = heappop(hq)[1]
    if val[0] <= cur_dat:
        ret+=val[1]
    else:
        heappush(hq,val)
    cur_dat+=1
print(ret)


Fixed submission:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))

from collections import defaultdict
from heapq import heappush, heappop
dd = defaultdict(list)

for _ in range(n):
    a,b = tuple(map(int,input().split()))
    dd[a].append(b)

hq = []
ret = 0
for i in range(1,m+1):
    for j in dd[i]:
        heappush(hq,-j)
    if hq:
        ret+=heappop(hq)
print(-ret)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import numpy as np
from copy import deepcopy
s = input()
cnt = 0
mod_13_cnt = np.array([0]*13)
hatena = [0,1,2,3,4,5,6,7,8,9]
#定数部分を評価
s_teisu = int(s.replace("?","0")) %13
mod_13_cnt[s_teisu]+=1
fn = lambda x : x %(10**9+7)
for i,s_i in enumerate(s[::-1]):
     mod_13_cnt = np.array(list(map(fn,mod_13_cnt)))
     ph = np.array([0]*13)
     if s_i!="?":
         continue
     for j in hatena:
         add_v = j*10**i%13
         ph += np.roll(mod_13_cnt,add_v)
     mod_13_cnt = ph
print(mod_13_cnt[5]%(10**9+7))

Fixed submission:
# -*- coding: utf-8 -*-
s = input()
s = s[::-1]
MOD = 10**9+7
mod13_map = [[i for i in range(13)]]
ma = mod13_map.append
for i in range(1,10**5):
    next_digit = list(map(lambda x:x*10%13,mod13_map[i-1]))
    ma(next_digit)

ret = [1] + [0] * 12 #13で割ってi余る数の合計
for i,v in enumerate(s):
    if v!="?":
        #mod13_map[i][v]だけ、右にシフト
        ret *= 2
        sft = mod13_map[i][int(v)]
        ret = ret[13-sft:26-sft]
    else:
        temp_ret = [0] * 13
        for j in range(10):
            #?がjの場合
            for k,l in enumerate(ret):
                temp_ret[(k+mod13_map[i][j])%13]+=l
        temp_ret = list(map(lambda x:x%MOD,temp_ret))
        ret = temp_ret
print(ret[5]%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import numpy as np
from copy import deepcopy
s = input()
cnt = 0
mod_13_cnt = np.array([0]*13)
hatena = [0,1,2,3,4,5,6,7,8,9]
#定数部分を評価
s_teisu = int(s.replace("?","0")) %13
mod_13_cnt[s_teisu]+=1
fn = lambda x : x %(10**9+7)
for i,s_i in enumerate(s[::-1]):
     mod_13_cnt = np.array(list(map(fn,mod_13_cnt)))
     ph = np.array([0]*13)
     if s_i!="?":
         continue
     for j in hatena:
         add_v = j*10**i%13
         ph += np.roll(mod_13_cnt,add_v)
     mod_13_cnt = ph
print(mod_13_cnt[5]%(10**9+7))


Fixed submission:
# -*- coding: utf-8 -*-
s = input()
s = s[::-1]
MOD = 10**9+7
mod13_map = [[i for i in range(13)]]
ma = mod13_map.append
for i in range(1,10**5):
    next_digit = list(map(lambda x:x*10%13,mod13_map[i-1]))
    ma(next_digit)

ret = [1] + [0] * 12 #13で割ってi余る数の合計
for i,v in enumerate(s):
    if v!="?":
        #mod13_map[i][v]だけ、右にシフト
        ret *= 2
        sft = mod13_map[i][int(v)]
        ret = ret[13-sft:26-sft]
    else:
        temp_ret = [0] * 13
        for j in range(10):
            #?がjの場合
            for k,l in enumerate(ret):
                temp_ret[(k+mod13_map[i][j])%13]+=l
        temp_ret = list(map(lambda x:x%MOD,temp_ret))
        ret = temp_ret
print(ret[5]%MOD)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
a = int(input())
c = [int(input()) for i in range(a)]

#最大値のindexを探し、最大値が複数あるか確認
all_max = max(c)
first_max_id = c.index(all_max)

c_dash = sorted(c,reversed=True)
second_max_value = c_dash[1]
for i,v in enumerate(c):
    if i != first_max_id:
        pr_val = all_max
    else:
        if all_max == second_max_value:
            pr_val = all_max
        else:
            pr_val = second_max_value
    print(pr_val)

Fixed submission:
# -*- coding: utf-8 -*-
a = int(input())
c = [int(input()) for i in range(a)]

#最大値のindexを探し、最大値が複数あるか確認
all_max = max(c)
first_max_id = c.index(all_max)

c_dash = sorted(c,reverse=True)
second_max_value = c_dash[1]
for i,v in enumerate(c):
    if i != first_max_id:
        pr_val = all_max
    else:
        if all_max == second_max_value:
            pr_val = all_max
        else:
            pr_val = second_max_value
    print(pr_val)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
ret = [0 for _ in range(n+1)]
#後ろから求める
for i,a_i in enumerate(a[-1::-1]):
    cur_ret_sum = sum(ret[n-i::n-i])%2
    if a_i!=cur_ret_sum:
        ret[n-i]=1

print(sum(ret[1::]))
print(" ".join(ret[1::]))

Fixed submission:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
ret = [0 for _ in range(n+1)]
#後ろから求める
for i,a_i in enumerate(a[-1::-1]):
    cur_ret_sum = sum(ret[n-i::n-i])%2
    if a_i!=cur_ret_sum:
        ret[n-i]=1
m = sum(ret[1::])
print(m)
if m > 0:
    print(" ".join([str(i) for i,v in enumerate(ret) if v==1]))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import math
a,b,c,d = list(map(int,input().split()))

lcm_cd = c*d//math.gcd(c,d)

a_div_c = a//c
ac_mod = a%c
bc = b//c

a_div_d = a//d
ad_mod = a%d
bd = b//d

a_div_lcm_cd = a//lcm_cd
alcm_cd_mod = a%lcm_cd
blcm_cd = b//lcm_cd

cnt_c = 0
cnt_d = 0
cnt_lcmcd = 0

cnt_c = (bc-a_div_c)
if not ac_mod:
    cnt_c+=1

cnt_d = (bd-a_div_d)
if not ad_mod:
    cnt_d+=1

cnt_lcmcd = (blcm_cd-a_div_lcm_cd)
if not alcm_cd_mod:
    cnt_lcmcd+=1
print(b-a+1-(cnt_c+cnt_d-cnt_lcmcd))


Fixed submission:
# -*- coding: utf-8 -*-
import fractions
a,b,c,d = list(map(int,input().split()))

lcm_cd = c*d//fractions.gcd(c,d)

a_div_c = a//c
ac_mod = a%c
bc = b//c

a_div_d = a//d
ad_mod = a%d
bd = b//d

a_div_lcm_cd = a//lcm_cd
alcm_cd_mod = a%lcm_cd
blcm_cd = b//lcm_cd

cnt_c = 0
cnt_d = 0
cnt_lcmcd = 0

cnt_c = (bc-a_div_c)
if not ac_mod:
    cnt_c+=1

cnt_d = (bd-a_div_d)
if not ad_mod:
    cnt_d+=1

cnt_lcmcd = (blcm_cd-a_div_lcm_cd)
if not alcm_cd_mod:
    cnt_lcmcd+=1
print(b-a+1-(cnt_c+cnt_d-cnt_lcmcd))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
cb = [[-c,b] for b,c in bc]
from heapq import heappush, heappop, heapify
ret = 0
heapify(a)
heapify(cb)
flg = True
while flg and len(cb)>0:
    c,j = heappop(cb)
    for _ in range(j):
        min_a = heappop(a)
        if min_a < -c:
            ret+=(-c)
        else:
            ret+=min_a
            flg=False
            break
ret+=sum(a)
print(ret)

Fixed submission:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
cb = [[-c,b] for b,c in bc]
from heapq import heappush, heappop, heapify
ret = 0
heapify(a)
heapify(cb)
flg = True
while flg and len(cb)>0:
    c,j = heappop(cb)
    for _ in range(j):
        if len(a)==0:
            flg=False
            break
        min_a = heappop(a)
        if min_a < -c:
            ret+=(-c)
        else:
            ret+=min_a
            flg=False
            break
ret+=sum(a)
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
d = [list(map(int,input().split())) for i in range(q)]

for i in d:
    print(s[i[0]-1:i[1]].count("AC"))


Fixed submission:
# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
s2 = s[1::]
d = [list(map(int,input().split())) for i in range(q)]

#AC開始位置を記録する
ac_idx = []

aci_append = ac_idx.append
for i,v in enumerate(zip(s,s2)):
    if v == ("A","C"):
        aci_append(i)

#2分探索, nibuntansaku,二分探索
from bisect import bisect_left

for l,r in d:
    print(bisect_left(ac_idx,r-1) - bisect_left(ac_idx,l-1))

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = list(map(int,input().split()))
S = input()
ac_index = [i for i in range(N-1) if S[i:i+2]=="AC"]

for _ in range(Q):
    l,r = list(map(int,input().split()))
    l = l - 1
    r = r - 1
    print(len([i for i in ac_index if i >= l and i < r]))


Fixed submission:
# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
s2 = s[1::]
d = [list(map(int,input().split())) for i in range(q)]

#AC開始位置を記録する
ac_idx = []

aci_append = ac_idx.append
for i,v in enumerate(zip(s,s2)):
    if v == ("A","C"):
        aci_append(i)

#2分探索, nibuntansaku,二分探索
from bisect import bisect_left

for l,r in d:
    print(bisect_left(ac_idx,r-1) - bisect_left(ac_idx,l-1))

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = list(map(int,input().split()))
S = input()

for _ in range(Q):
    l,r = list(map(int,input().split()))
    print(S[l-1:r].count("AC"))


Fixed submission:
# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
s2 = s[1::]
d = [list(map(int,input().split())) for i in range(q)]

#AC開始位置を記録する
ac_idx = []

aci_append = ac_idx.append
for i,v in enumerate(zip(s,s2)):
    if v == ("A","C"):
        aci_append(i)

#2分探索, nibuntansaku,二分探索
from bisect import bisect_left

for l,r in d:
    print(bisect_left(ac_idx,r-1) - bisect_left(ac_idx,l-1))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
N,M = list(map(int,input().split()))

res_dict = {0:0}
for _ in range(N):
    #M本になるまでは買い続け、M本より多くなった場合は、価格の高いものから
    a,b = list(map(int,input().split()))
    cur_max_price = max(res_dict.keys())
    if sum(res_dict.values()) - M < 0 or a < cur_max_price:
        #追加操作
        if a in res_dict:
            res_dict[a] += b
        else:
            res_dict[a] = b
    decrease = sum(res_dict.values()) - M
    while decrease > 0:
        max_price = max(res_dict.keys())
        if decrease < res_dict[max_price]:
            res_dict[max_price] -= decrease
            break
        else:
            decrease -= res_dict[max_price]
            res_dict.pop(max_price)

print(sum([k * v for k,v in res_dict.items()]))


Fixed submission:
# -*- coding: utf-8 -*-
N,M = list(map(int,input().split()))

l = [list(map(int,input().split())) for _ in range(N)]
l = sorted(l, key=lambda x:x[0])
a_cnt = 0
b_cnt = 0
for a,b in l:
    if b <= M:
        b_cnt += b
        M -= b
        a_cnt += a*b
    elif b > M and M > 0:
        b_cnt += M
        a_cnt += a*M
        break
    else:
        break
print(a_cnt)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from copy import copy
a = list(map(int,input()))
cur_min = 100001
def remove_max(cubes):
    global cur_min
    for i in range(len(cubes)-1):
        if cubes[i] != cubes[i+1]:
            z = copy(cubes)
            z.pop(i)
            z.pop(i)
            if len(z) == 0:
                cur_min=0
            if len(z) <= cur_min:
                cur_min = len(z)
                remove_max(z)
remove_max(a)
if cur_min==100001:
    print(0)
else:
    print(len(a) - cur_min)


Fixed submission:
# -*- coding: utf-8 -*-
a = input()
len_a = len(a)
sum_a = sum(list(map(int,list(a))))
ret = min(sum_a,len_a-sum_a) * 2
print(ret)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from copy import copy
a = list(input())
cur_min = 100001
def remove_max(cubes):
    global cur_min
    for i in range(len(cubes)-1):
        if cubes[i] != cubes[i+1]:
            z = copy(cubes)
            z.pop(i)
            z.pop(i)
            if len(z) == 0:
                cur_min=0
            if len(z) <= cur_min:
                cur_min = len(z)
                remove_max(z)
remove_max(a)
if cur_min==100001:
    print(0)
else:
    print(len(a) - cur_min)


Fixed submission:
# -*- coding: utf-8 -*-
a = input()
len_a = len(a)
sum_a = sum(list(map(int,list(a))))
ret = min(sum_a,len_a-sum_a) * 2
print(ret)
Buggy python submission (verdict: Runtime Error):
a = int(input())
if a <= "2019/04/30":
  print("Heisei")
else:
  print("TBD")

Fixed submission:
a = input()
if a <= "2019/04/30":
  print("Heisei")
else:
  print("TBD")
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
a = int(input())
total = 0
for _ in range(a):
    i = input()
    v,c = i.split()
    v = int(v)
    if(c=="BTC"):
        v *= 380000
    total += v
print(total)


Fixed submission:
a = int(input())
total = 0
for _ in range(a):
    i = input()
    v,c = i.split()
    v = float(v)
    if(c=="BTC"):
        v *= 380000
    total += v
print(total)

Buggy python submission (verdict: Runtime Error):
a = int(input())
total = 0
for i in range(a):
    v,c = i.split()
    v = int(v)
    if(c=="BTC"):
        v *= 380000
    total += v
print(total)


Fixed submission:
a = int(input())
total = 0
for _ in range(a):
    i = input()
    v,c = i.split()
    v = float(v)
    if(c=="BTC"):
        v *= 380000
    total += v
print(total)

Buggy python submission (verdict: Runtime Error):
a = int(input())
total = 0
for i in range(a):
    v,c = i.split()[0]
    v = int(v)
    if(c=="BTC"):
        v *= 380000
    total += v
print(total)

Fixed submission:
a = int(input())
total = 0
for _ in range(a):
    i = input()
    v,c = i.split()
    v = float(v)
    if(c=="BTC"):
        v *= 380000
    total += v
print(total)