Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline
# intin = map( int, readline().rstrip().split() )

N = int(input())
S = input()

ans = 0
for x in range(0,1000):
    x = str(x)
    if len(x) == 1:
        x = "00" + x
    elif len(x) == 2 :
        x = "0" + x
    index = 0
    for s in S:
        if x[index] == s:
            index += 1
        if index == 3:
            ans += 1
            break

print(ans)

Fixed submission:
import sys
readline = sys.stdin.readline
# intin = map( int, readline().rstrip().split() )

N = int(input())
S = input()

# 10^4 * 10^3 * 3 = 3* (10 ^7)

ans = 0
for x in range(0,1000):
    x = str(x)
    if len(x) == 1:
        x = "00" + x
    elif len(x) == 2 :
        x = "0" + x
    index = 0
    for s in S:
        if x[index] == s:
            index += 1
        if index == 3:
            ans += 1
            break

print(ans)
Buggy python submission (verdict: Runtime Error):
I = input()
I = I.split(" ")
N = I[0]
K = I[1]
Q = I[2]

A = [0]*Q

for i in range(Q):
	A[i] = int(input())

point = [0]*N

for i in range(Q):
	point[A[i]-1] = point[A[i]-1] + 1

for i in range(Q):
	if point[i] > 0:
		print("yes")
	else:
		print("no")

Fixed submission:
str = input()

if str == "Sunny":
	print("Cloudy")
elif str == "Rainy":
	print("Sunny")
else:
	print("Rainy")
Buggy python submission (verdict: Runtime Error):
N , K = map(int,input().split())
h = list(map(int,input().split()))

def dp(cost):
    for x in range(1,N):
        cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

if __name__ == "__main__":
    solve()

Fixed submission:
#frog
N = int(input())
h = list(map(int,input().split()))
dp = [10000000000000] * N
dp[0] = 0

def dpf():
    for i in range(1,N):
        x = abs( h[i] - h[i-1] ) + dp[i-1]
        y = abs( h[i] - h[i-2] ) + dp[i-2]
        if x >=y:
            dp[i] = y
        else:
            dp[i] = x

def solve():
    dpf()
    print(dp[N-1])

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    white -= max(0,visit[(H-2)*W+W-2])
    if white == 0:
        return -1
    else:
        return white


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)

Fixed submission:
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    length = visit[(H-2)*W+W-2]
    if  length == -1:
        return -1
    else:
        return white - length


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)
Buggy python submission (verdict: Runtime Error):
S = input()

i = 0
while i + 1 <= len(S):
    if S[i] == 'h' and S[i+1] == 'i':
        i += 2
    else:
        break

if i == len(S):
    print('Yes')
else:
    print('No')


Fixed submission:
S = input()

i = 0
if len(S) % 2 != 0:
    print('No')
    exit()

while i + 1 <= len(S):
    if S[i] == 'h' and S[i+1] == 'i':
        i += 2
    else:
        break

if i == len(S):
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 200000

for i in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)

for aa in a:
    for bb in b:
        ans = min(ans, aa + bb)

print(ans)


Fixed submission:
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 200000

for i in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)


ans = min(ans, min(a) + min(b))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 200000

for i in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)

for aa in a:
    for bb in b:
        ans = min(ans, aa + bb)

print(ans)


Fixed submission:
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 200000

for i in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)


ans = min(ans, min(a) + min(b))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))


Fixed submission:
H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**9] * (lim + 1)
dp[0] = 0

for h in range(lim + 1):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]
        if 0 < rem:
            cns += dp[rem]

        dp[h] = min(cns, dp[h])

print(min(dp[H:lim+1]))


Fixed submission:
H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for n in range(N):
    A[n], B[n] = map(int, input().split())

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))
Buggy python submission (verdict: Time Limit Exceeded):
import queue

D = ((0, 1), (1, 0), (0, -1), (-1, 0))

def bfs(M, s, g):

    if s == g:
        return 0

    q = queue.Queue()
    q.put((s[0], s[1], 0))

    while not q.empty():
        cur = q.get()

        for d in D:
            x = cur[0] + d[0]
            y = cur[1] + d[1]
            if M[y][x] != '#':
                if (x, y) == g:
                    return cur[2] + 1
                else: 
                    q.put((x, y, cur[2]+1))

    return 20*20+1

H, W = map(int, input().split())
S = [None]*(H+2)

S[0] = '#' * (W + 2)
for h in range(1, H+1):
    S[h] = '#' + input() + '#'
S[-1] = '#' * (W + 2)

ans = 0
for sy in range(1, H+1):
    for sx in range(1, W+1):
        if S[sy][sx] != '#':
            for gy in range(sy, H+1):
                for gx in range(1, W+1):
                    if S[gy][gx] != '#' and not (sy == gy and gx < sx):
                        ans = max(ans, bfs(S, (sx, sy), (gx, gy)))

print(ans)

Fixed submission:
import queue
import copy
D = ((0, -1), (0, 1), (-1, 0), (1, 0))

def bfs(S, s):
    M = copy.deepcopy(S)
    M[s[1]][s[0]] = '#'
    q = queue.Queue()
    q.put((s[0], s[1], 0))
    dis = 0

    while not q.empty():
        cur = q.get()

        for d in D:
            x = cur[0] + d[0]
            y = cur[1] + d[1]
            if M[y][x] != '#':
                M[y][x] = '#'
                q.put((x, y, cur[2]+1))
                dis = max(dis, cur[2]+1)

    return dis


H, W = map(int, input().split())
S = [None]*(H+2)

S[0] = ['#'] * (W + 2)
for h in range(1, H+1):
    S[h] = ['#'] + [c for c in input()] + ['#']
S[-1] = ['#'] * (W + 2)

ans = 0
for sy in range(1, H+1):
    for sx in range(1, W+1):
        if S[sy][sx] != '#':
            ans = max(ans, bfs(S, (sx, sy)))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

ans = 0
for n in range(1, N):
    ans += n
print(ans)


Fixed submission:
N = int(input())

print((N-1)*(1+N-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [[0, 0] for _ in range(N)]

for n in range(N):
    AB[n][0], AB[n][1] = map(int, input().split())
    AB[n][1] = 0 - AB[n][1]
AB.sort()

pop_list = []

earn = 0
for m in range(1, M + 1):
    max_earn = 0
    max_i = 0
    for i in range(len(AB)):
        if m < AB[i][0]:
            break

        if max_earn > AB[i][1] and i not in pop_list:
            max_earn = AB[i][1]
            max_i = i

    if max_earn != 0:
        earn += AB[max_i][1]
        pop_list.append(max_i)

print(0 - earn)


Fixed submission:
import queue

N, M = map(int, input().split())
AB = [[] for _ in range(M + 1)]

for n in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    AB[a].append(0-b)

earn = 0
q = queue.PriorityQueue()

for m in range(1, M + 1):

    for job in AB[m]:
        q.put(job)

    if not q.empty():
        earn += q.get()

print(0-earn)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [[0, 0] for _ in range(N)]

for n in range(N):
    AB[n][0], AB[n][1] = map(int, input().split())
    AB[n][1] = 0 - AB[n][1]
AB.sort()

earn = 0
for m in range(1, M+1):
    max_earn = 0
    max_i = 0
    for i in range(len(AB)):
        if m < AB[i][0] :
            break
        
        if max_earn > AB[i][1]:
            max_earn = AB[i][1]
            max_i = i


    if max_earn != 0:
        earn += AB[max_i][1]
        AB.pop(max_i)

        

        
print(0-earn)


Fixed submission:
import queue

N, M = map(int, input().split())
AB = [[] for _ in range(M + 1)]

for n in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    AB[a].append(0-b)

earn = 0
q = queue.PriorityQueue()

for m in range(1, M + 1):

    for job in AB[m]:
        q.put(job)

    if not q.empty():
        earn += q.get()

print(0-earn)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [[0, 0] for _ in range(N)]

for n in range(N):
    AB[n][0], AB[n][1] = map(int, input().split())
    AB[n][1] = 0 - AB[n][1]
AB.sort()

earn = 0
for m in range(1, M+1):
    max_earn = 0
    max_i = 0
    for i in range(len(AB)):
        if m < AB[i][0] :
            break
        
        if max_earn > AB[i][1]:
            max_earn = AB[i][1]
            max_i = i


    if max_earn != 0:
        earn += AB[max_i][1]
        AB.pop(max_i)

        

        
print(0-earn)


Fixed submission:
import queue

N, M = map(int, input().split())
AB = [[] for _ in range(M + 1)]

for n in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    AB[a].append(0-b)

earn = 0
q = queue.PriorityQueue()

for m in range(1, M + 1):

    for job in AB[m]:
        q.put(job)

    if not q.empty():
        earn += q.get()

print(0-earn)
Buggy python submission (verdict: Runtime Error):
N = input()
ans = 0
for n in range(1, len(N), 2):
    ans += 9 * 10 ** (n-1)

if len(N) % 2 != 0:
    ans += ans * (int(N[0]) - 1)
    ans += int(N[1:]) + 1

print(ans)


Fixed submission:
N = input()
ans = 0
for n in range(1, len(N), 2):
    ans += 9 * 10 ** (n-1)

if len(N) == 1:
    ans = int(N)


elif len(N) % 2 != 0:
    ans += (10 ** (len(N)-1)) * (int(N[0])-1)
    ans += int(N[min(1, len(N)-1):]) + 1


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

ans = [0] * len(S)

for i in range(len(S)):
    if S[i] == 'R':
        for j in range(i+1, len(S)):
            if S[j] == 'L':
                if (j - i) % 2 == 0:
                    ans[j] += 1
                else:
                    ans[j-1] += 1
                break

    else:
        for j in range(i-1, -1, -1):
            if S[j] == 'R':
                if (i-j) % 2 == 0:
                    ans[j] += 1
                else:
                    ans[j+1] += 1
                break

print(*ans)


Fixed submission:
S = input() + 'R'

ans = [0] * len(S)

cur = 'R'
cur_i = 0
points = []


for i in range(len(S)):
    if cur != S[i]:
        if S[i] == 'L':
            diff = i - cur_i
            if diff % 2 == 0:
                ans[i-1] += int(diff/2)
                ans[i] += int(diff/2)
            else:
                ans[i-1] += int((diff+1)/2)
                ans[i] += int((diff-1)/2)

            cur_i = i
            cur = 'L'

        if S[i] == 'R':
            diff = i - cur_i
            if diff % 2 == 0:
                ans[cur_i-1] += int(diff/2)
                ans[cur_i] += int(diff/2)
            else:
                ans[cur_i-1] += int((diff-1)/2)
                ans[cur_i] += int((diff+1)/2)

            cur_i = i
            cur = 'R'


print(*ans[:-1])

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

ans = [0] * len(S)

for i in range(len(S)):
    if S[i] == 'R':
        for j in range(i+1, len(S)):
            if S[j] == 'L':
                if (j - i) % 2 == 0:
                    ans[j] += 1
                else:
                    ans[j-1] += 1
                break

    else:
        for j in range(i-1, -1, -1):
            if S[j] == 'R':
                if (i-j) % 2 == 0:
                    ans[j] += 1
                else:
                    ans[j+1] += 1
                break

print(*ans)


Fixed submission:
S = input() + 'R'

ans = [0] * len(S)

cur = 'R'
cur_i = 0
points = []


for i in range(len(S)):
    if cur != S[i]:
        if S[i] == 'L':
            diff = i - cur_i
            if diff % 2 == 0:
                ans[i-1] += int(diff/2)
                ans[i] += int(diff/2)
            else:
                ans[i-1] += int((diff+1)/2)
                ans[i] += int((diff-1)/2)

            cur_i = i
            cur = 'L'

        if S[i] == 'R':
            diff = i - cur_i
            if diff % 2 == 0:
                ans[cur_i-1] += int(diff/2)
                ans[cur_i] += int(diff/2)
            else:
                ans[cur_i-1] += int((diff-1)/2)
                ans[cur_i] += int((diff+1)/2)

            cur_i = i
            cur = 'R'


print(*ans[:-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = list(map(int, input().split(' ')[:-1]))
b = [0 for _ in range(N)]

a.insert(0, 0)
b.insert(0, 0)

n = int(N/2)

for i in range(N, 0, -1):
    nums = 0

    for ii in range(2, int(N/i)):
        nums += b[i*ii - 1]

    if nums % 2 != a[i]:
        b[i] += 1

sum_b = sum(b)
print(sum_b)

flag = True
for i, bb in enumerate(b):
    if i == 0:
        continue

    if bb != 0:
        flag = False
        print(i, end=' ')

if flag:
    print()


Fixed submission:
N = int(input())
a = list(map(int, input().split(' ')))
b = [0 for _ in range(N)]

a.insert(0, 0)
b.insert(0, 0)

n = int(N/2)

for i in range(N, 0, -1):
    nums = 0
    for ii in range(2, int(N/i)+1):
        nums += b[i*ii]

    if nums % 2 != a[i]:
        b[i] += 1

sum_b = sum(b)
print(sum_b)

flag = False
for i, bb in enumerate(b):
    if i == 0:
        continue

    if bb != 0:
        flag = True
        print(i, end=' ')

if flag:
    print()
Buggy python submission (verdict: Runtime Error):
X, A = map(int, input())
if X < A:
    print(0)
else:
    print(10)


Fixed submission:
X, A = map(int, input().split(' '))
if X < A:
    print(0)
else:
    print(10)

Buggy python submission (verdict: Runtime Error):
X, A = int(input().split(''))
if X < A:
    print(0)
else:
    print(10)


Fixed submission:
X, A = map(int, input().split(' '))
if X < A:
    print(0)
else:
    print(10)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
L = map(int, input().split())

D = 0
count = 1

for l in L:
    D += l

    if D <= X:
        count += 1

    else:
        breakXh

print(count)


Fixed submission:
N, X = map(int, input().split())
L = map(int, input().split())

D = 0
count = 1

for l in L:
    D += l

    if D <= X:
        count += 1

    else:
        break

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

mod = 1000000007

dp = [0 for _ in range(N + 1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

for n in range(2, N + 1):
    if n in A:
        dp[n] = 0
    else:
        dp[n] = dp[n - 1] + dp[n - 2]
        if dp[n] >= mod:
            dp[n] -= mod
            
print(dp[N])


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

mod = 1000000007

dp = [1 for _ in range(N + 1)]
for a in A:
    dp[a] = 0

for n in range(2, N + 1):
    dp[n] *= dp[n - 1] + dp[n - 2]

    if dp[n] >= mod:
        dp[n] -= mod

print(dp[N])

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

mod = 1000000007

dp = [0 for _ in range(N + 1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

for n in range(2, N + 1):
    if n in A:
        dp[n] = 0
    else:
        dp[n] = dp[n - 1] + dp[n - 2]
        if dp[n] >= mod:
            dp[n] -= mod
            
print(dp[N])


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

mod = 1000000007

dp = [1 for _ in range(N + 1)]
for a in A:
    dp[a] = 0

for n in range(2, N + 1):
    dp[n] *= dp[n - 1] + dp[n - 2]

    if dp[n] >= mod:
        dp[n] -= mod

print(dp[N])

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

mod = 1000000007

dp = [0 for _ in range(N + 1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

for n in range(2, N + 1):
    if n in A:
        dp[n] = 0
    else:
        dp[n] = (dp[n - 1] + dp[n - 2]) % mod

print(dp[N])


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

mod = 1000000007

dp = [1 for _ in range(N + 1)]
for a in A:
    dp[a] = 0

for n in range(2, N + 1):
    dp[n] *= dp[n - 1] + dp[n - 2]

    if dp[n] >= mod:
        dp[n] -= mod

print(dp[N])

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

mod = 1000000007

dp = [0 for _ in range(N + 1)]
dp[0] = 1
if 1 not in A:
    dp[1] = 1

for n in range(2, N + 1):
    if n in A:
        dp[n] = 0
    else:
        dp[n] = (dp[n - 1] + dp[n - 2]) % mod

print(dp[N])


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

mod = 1000000007

dp = [1 for _ in range(N + 1)]
for a in A:
    dp[a] = 0

for n in range(2, N + 1):
    dp[n] *= dp[n - 1] + dp[n - 2]

    if dp[n] >= mod:
        dp[n] -= mod

print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
AC = [0 for _ in range(N)]
flag_A = False
for i, s in enumerate(input()):
    if flag_A:
        if s == 'C':
            AC[i-1] = 1
        flag_A = False

    elif s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(sum(AC[l-1:r-1:]))


Fixed submission:
N, Q = map(int, input().split())
AC = [None] * N
flag_A = False
cnt = 0
for i, s in enumerate(input()):
    AC[i] = cnt
    if flag_A:
        if s == 'C':
            cnt += 1
            AC[i] = cnt
        flag_A = False

    if s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(AC[r-1] - AC[l-1])

Buggy python submission (verdict: Runtime Error):
N, Q = map(int, input().split())
AC = [0 for _ in range(N)]
flag_A = False
for i, s in enumerate(input()):
    if flag_A:
        if s == 'C':
            AC[i-1] = 1
        flag_A = False

    elif s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(sum(AC[l-1:r-1:]))


Fixed submission:
N, Q = map(int, input().split())
AC = [None] * N
flag_A = False
cnt = 0
for i, s in enumerate(input()):
    AC[i] = cnt
    if flag_A:
        if s == 'C':
            cnt += 1
            AC[i] = cnt
        flag_A = False

    if s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(AC[r-1] - AC[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
AC = [0 for _ in range(N)]
flag_A = False
for i, s in enumerate(input()):
    if flag_A:
        if s == 'C':
            AC[i-1] = 1
        flag_A = False

    elif s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(sum(AC[l-1:r-1:]))


Fixed submission:
N, Q = map(int, input().split())
AC = [None] * N
flag_A = False
cnt = 0
for i, s in enumerate(input()):
    AC[i] = cnt
    if flag_A:
        if s == 'C':
            cnt += 1
            AC[i] = cnt
        flag_A = False

    if s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(AC[r-1] - AC[l-1])