Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N=int(input())
dst = [[0, 0, 0]]
for i in range(N):
    dst.append(input().split())
    
flag = True

for i in range(1, N+1):
    time_diff = int(dst[i][0])-int(dst[i-1][0])
    dst_diff = int(dst[i][1])-int(dst[i-1][1])+int(dst[i][2])-int(dst[i-1][2])
    if (time_diff>=dst_diff and time_diff%2 == dst_diff%2):
        continue
    else:
        flg = False
        break

if flg == True:
    print('Yes')
else:
    print('No')

Fixed submission:
N=int(input())
dst = [[0, 0, 0]]
for i in range(N):
    dst.append(input().split())
    
flag = True

for i in range(1, N+1):
    time_diff = int(dst[i][0])-int(dst[i-1][0])
    dst_diff = abs(int(dst[i][1])-int(dst[i-1][1]))+abs(int(dst[i][2])-int(dst[i-1][2]))
    if (time_diff>=dst_diff and (time_diff+2)%2 == (dst_diff+2)%2):
        flg = True
    else:
        flg = False
        break

if flg == True:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
array = [int(x) for x in input().split(' ')]
s = 0
for i in range(n):
    for j in range(i+1, n):
        s += (array[i] * array[j])

print(s % (10 ** 9 + 7))

Fixed submission:
n = int(input())
array = [int(x) for x in input().split(' ')]
s = 0
sums = []
for i in range(n-1, -1, -1):
    if i == n-1:
        sums.append(array[i])
    else:
        sums.append(sums[-1] + array[i])

sums.pop()
for i in range(n-1):
    s += array[i] * sums.pop()

print(s % (10 ** 9 + 7))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
divs = [0]*(N+1)
for i in range(1, N+1):
    for j in range(1, N//i + 1):
        divs[i*j] += 1

ans = 0
for i in range(N+1):
    ans += i*divs[i]

print(ans)




Fixed submission:
N = int(input())
ans = 0
for i in range(1, N+1):
    Ni = N // i
    ans += i*Ni*(Ni+1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6 + 1)
for i in range(n):
    for j in range(1, 10**6//a[i]+1):
        num[a[i]*j] += 1

ans = 0
for i in range(n):
    if num[a[i]] < 2:
        ans += 1

# print(num[:30])
print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6+1)
for x in a:
    if num[x] != 0:
        num[x] = 2
        continue
    for i in range(x, 10**6+1, x):
        num[i] += 1

ans = 0
for x in a:
    if num[x] == 1:
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
mod = -1
num = [0]
prev = 0
cnt = 0
# num.append(0)
while True:
    # print(num, cnt)
    if not a[prev] in num:
        num.append(a[prev])
        prev = a[prev]
    else:
        lpst = a[prev] 
        mod = cnt - num.index(a[prev]) + 1
        break
    cnt += 1

# print(mod, lpst)
now = 0
while k > 0:
    if now == lpst:
        k %= mod
    if k == 0:
        break
    now = a[now]
    k -= 1
    # print(now, k)


print(now+1)

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
used = set()
num = [0]*n
used.add(0)
now = 0
cnt = 0
while True:
    cnt += 1
    if not a[now] in used:
        used.add(a[now])
        num[a[now]] = cnt
        now = a[now]
    else:
        lps = a[now]
        mod = cnt - num[a[now]]
        # k %= mod
        break
now = 0
# print(mod, lps, k, num)
while k:
    if now == lps:
        k %= mod
    if k == 0:
        break
    now = a[now]
    k -= 1

print(now+1)
Buggy python submission (verdict: Time Limit Exceeded):
import math
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            temp = math.gcd(i, j)
            ans += math.gcd(temp, k)

print(ans)


Fixed submission:
import math
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            temp = math.gcd(i, j)
            ans += math.gcd(temp, k)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n, x, y = map(int,input().split()) #n:頂点数　w:辺の数
w = n
ans = [0 for _ in range(n-1)]
# print(ans)
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w-1):
    # x,y = map(int,input().split())
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

# print(dijkstra(0,n,w,cost))
for i in range(n-1):
    aa = dijkstra(i, n, w, cost)
    # print(aa)
    for j in range(i+1, n):
        ans[aa[j]] += 1
ans = ans[1:] + [0]
# print(*ans)
for A in ans:
    print(A)

Fixed submission:
n, x, y = map(int, input().split())
ans = [0 for _ in range(n-1)]
for i in range(1, n):
    for j in range(i+1, n+1):
        d = min(j-i, abs(x-i) + abs(y-j) + 1)
        ans[d-1] += 1

print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n, x, y = map(int,input().split()) #n:頂点数　w:辺の数
w = n
ans = [0 for _ in range(n-1)]
# print(ans)
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w-1):
    # x,y = map(int,input().split())
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

# print(dijkstra(0,n,w,cost))
for i in range(n-1):
    aa = dijkstra(i, n, w, cost)
    # print(aa)
    for j in range(i+1, n):
        ans[aa[j]] += 1
ans = ans[1:] + [0]
# print(*ans)
for A in ans:
    print(A)

Fixed submission:
n, x, y = map(int, input().split())
ans = [0 for _ in range(n-1)]
for i in range(1, n):
    for j in range(i+1, n+1):
        d = min(j-i, abs(x-i) + abs(y-j) + 1)
        ans[d-1] += 1

print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n, a, b = map(int, input().split())
mod = 10**9 + 7
# def pow1(x, n):
#     if n == 0: return 1
#     value = pow1(x, int(n / 2)) % mod
#     value *= value % mod
#     if n % 2 == 1: value *= x
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x
all = (pow_k(2, n) % mod) - 1
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

all -= cmb(n, a) + cmb(n, b)
print(all % mod)

Fixed submission:
n, a, b = map(int, input().split())
mod = 10**9 + 7
def inv(a, p):
    return pow(a, p-2, p)

def comb(n, r, p = mod):
    x, y = 1, 1
    for i in range(r):
        x = (x * (n - i)) % p
        y = (y * (i + 1)) % p
    return x * inv(y, p) % p

answer = (pow(2, n, mod) - 1 - comb(n, a) - comb(n, b)) % mod
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))
ev = []
for pi in p:
    Sum = 0
    for i in range(pi+1):
        Sum += i
    ev.append(Sum / pi)

ans = 0
cost = sum(ev[:k])
for i in range(k, n+1):
    if ans < cost:
        ans = cost
    if i == n:
        continue
    cost -= ev[i-k]
    cost += ev[i]
    # print(i)

print(ans)
# print(ev)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))
ev = []
for pi in p:
    ev.append((pi + 1) / 2)

ans = 0
cost = sum(ev[:k])
for i in range(k, n+1):
    if ans < cost:
        ans = cost
    if i == n:
        continue
    cost -= ev[i-k]
    cost += ev[i]
    # print(i)

print(ans)
# print(ev)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))
ev = []
for pi in p:
    Sum = 0
    for i in range(pi+1):
        Sum += i
    ev.append(Sum / pi)

ans = 0
for i in range(n-k+1):
    cost = sum(ev[i:i+k])
    if ans < cost:
        ans = cost

print(ans)
# print(ev)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))
ev = []
for pi in p:
    ev.append((pi + 1) / 2)

ans = 0
cost = sum(ev[:k])
for i in range(k, n+1):
    if ans < cost:
        ans = cost
    if i == n:
        continue
    cost -= ev[i-k]
    cost += ev[i]
    # print(i)

print(ans)
# print(ev)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))
# print(AB)
f_inf = float('inf')
dp = [f_inf] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in AB:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[H])

Fixed submission:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))
# print(AB)
f_inf = float('inf')
dp = [f_inf] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in AB:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[H])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))
answer = 1
for i in range(1, N):
    MIN = min(P[0:i])
    if MIN > P[i]:
        answer += 1

print(answer)

Fixed submission:
N = int(input())
P = list(map(int, input().split()))

def init_min(init_min_val):
    #set_val
    for i in range(N):
        seg_min[i+num_min-1]=init_min_val[i]    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
    
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_min = 10**10

#num_min:n以上の最小の2のべき乗
num_min =2**(N-1).bit_length()
seg_min=[ide_ele_min]*2*num_min
init_min(P)

answer = 1

for i in range(1, N):
    MIN = query_min(0, i)
    if MIN > P[i]:
        answer += 1

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))
answer = 0
for i in range(N):
    key = 1
    for j in range(i):
        # key = 1
        if P[i] > P[j]:
            key *= 0
        # print(P[i],P[j], key, answer)

    if key:
        answer += 1

print(answer)

Fixed submission:
N = int(input())
P = list(map(int, input().split()))

def init_min(init_min_val):
    #set_val
    for i in range(N):
        seg_min[i+num_min-1]=init_min_val[i]    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
    
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_min = 10**10

#num_min:n以上の最小の2のべき乗
num_min =2**(N-1).bit_length()
seg_min=[ide_ele_min]*2*num_min
init_min(P)

answer = 1

for i in range(1, N):
    MIN = query_min(0, i)
    if MIN > P[i]:
        answer += 1

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
pairs = []
answer = 0
def StartEnd(x):
    start = str(x)[0]
    end = str(x)[-1]
    return int(start), int(end)

for i in range(1, N+1):
    pair = ()
    a, b = StartEnd(i)
    pair += (a, b)
    pairs.append(pair)
    
for i in range(N):
    p = pairs[i]
    q = p[::-1]
    answer += pairs.count(q)
    
print(answer)    



Fixed submission:
N = int(input())
numMap = {}
answer = 0
def StartEnd(x):
    start = str(x)[0]
    end = str(x)[-1]
    return start, end

for i in range(1, N+1):
    # print('numMap:', numMap)
    pair = StartEnd(i)
    if pair in numMap:
        numMap[pair] += 1
    else:
        numMap[pair] = 1

for i in range(1, N+1):
    key = StartEnd(i)
    rev = key[::-1]
    # print('rev:', rev)
    if rev in numMap:
        answer += numMap[rev]
    
print(answer)
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

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

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

N = int(input())
A = list(map(int, input().split()))
answer = 0
mod = 10**9 + 7
# print(*A)
# print(lcm(*A))
LCM = lcm(*A)

for i in range(N):
    answer += LCM // A[i]

print(answer % mod)

Fixed submission:
from fractions import gcd
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

N = int(input())
A = list(map(int, input().split()))
answer = 0
mod = 10**9 + 7
LCM = lcm(*A)

for i in range(N):
    answer += LCM // A[i]

print(answer % mod)
Buggy python submission (verdict: Runtime Error):
ta, ao, K = map(int, input().split())
if K - ta > 0:
    taa = 0
    if ao - (K - ta) > 0:
        ao = ao - (K - ta)
    else:
        ao = 0
else:
    ta -= K


print(taa, ao)

Fixed submission:
Taka, Aoki, K = map(int, input().split())
dif = Taka - K
if dif >= 0:
    Taka -= K
else:
    dif = abs(dif)
    Taka = 0
    dif = Aoki - dif
    if dif >= 0:
        Aoki = dif
    else:
        Aoki = 0
print(Taka, Aoki)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
while True:
    judge = 1
    for i in range(2, N):
        if N % i == 0:
            judge *= N % i  #素数だとjudgeが0にならない
            break
        else:
            judge *= N % i  #素数だとjudgeが0にならない
    if judge >= 1:
        print(N)
        exit()
    N += 1

Fixed submission:
import math

def is_prime(n):
    for k in range(2, int(math.sqrt(n)+1)):
        if n % k == 0:
            return False
    return True

N = int(input())
while True:
    if is_prime(N):
        print(N)
        exit()
    N += 1
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())
def lcm(x, y):
    return (x * y) // math.gcd(x,y)

print(lcm(A, B))

Fixed submission:
A, B = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(lcm(A, B))
Buggy python submission (verdict: Runtime Error):
X = int(input())
dp = [0]*(X+1)
dp[0] = 1
dp[100] = 1
dp[101] = 1
dp[102] = 1
dp[103] = 1
dp[104] = 1
dp[105] = 1
for i in range(100, X+1):
    for j in range(6):
        dp[i] = max(dp[i], dp[i-100+j])

if dp[X]:
    print('Yes')
else:
    print('No')

Fixed submission:
import sys
X = int(input())
if 1 <= X and X < 100:
    print("0")
    sys.exit()
i = 0
dp = [0]*(X+1)
dp[0] = 1
for i in range(100, X+1):
    for j in range(6):
        if dp[i-(100+j)] == 0:
            pass
        else:
            dp[i] = 1
print(dp[X])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = 0
for i in range(1000):
    pw = str(i).zfill(3)
    ok1 = False
    ok2 = False
    ok3 = False
    for j in range(N):
        if S[j] == pw[0] and not ok1:
            ok1 = True
            continue
        if ok1 and not ok2:
            if S[j] == pw[1]:
                ok2 = True
                continue
        if ok2:
            if S[j] == pw[2]:
                ok3 = True
                # print(pw)
                break
    if ok3:
        ans += 1

print(ans)


Fixed submission:
N = int(input())
S = input()
ans = 0
for i in range(1000):
    pw = str(i).zfill(3)
    ok1 = False
    ok2 = False
    ok3 = False
    for j in range(N):
        if S[j] == pw[0] and not ok1:
            ok1 = True
            continue
        if ok1 and not ok2:
            if S[j] == pw[1]:
                ok2 = True
                continue
        if ok2:
            if S[j] == pw[2]:
                ok3 = True
                # print(pw)
                break
    if ok3:
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
    ans.append(a.index(i+1)+1)

print(*ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
info = []
ans = []
for i in range(n):
    info.append([a[i], i+1])
# print(info)
info.sort()
for s, o in info:
    print(o)
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = list(map(int, input().split()))
sv = h[n-1]
ok = True
for i in range(n-1):
    if h[i] - sv - 1 >= 2:
        ok = False

if ok:
    print('Yes')
else:
    print('No')

Fixed submission:
a, b, c = map(int, input().split())
if a - b < c:
    ans = c - (a - b)
else:
    ans = 0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

divs = make_divisors(s)
n = len(divs)
if n%2 == 0:
    print(0, 0, divs[n//2-1], 0, divs[n//2-1], divs[n//2])
else:
    print(0, 0, divs[n//2], 0, divs[n//2], divs[n//2])
# print(divs)


Fixed submission:
s = int(input())
x3 = (10**9-s%10**9)%10**9
y3 = (s+x3)//10**9
print(0, 0, 10**9, 1, x3, y3)
Buggy python submission (verdict: Runtime Error):
import collections
n = int(input())
balls = []
for _ in range(n):
    x, y = map(int, input().split())
    balls.append([x, y])
# print(balls)
delta = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]
        delta.append((dx, dy))

c_delta = collections.Counter(delta)
# print(c_delta)
print(n-c_delta.most_common()[0][1])

Fixed submission:
import collections
n = int(input())
balls = []
for _ in range(n):
    x, y = map(int, input().split())
    balls.append([x, y])
# print(balls)
delta = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]
        delta.append((dx, dy))

c_delta = collections.Counter(delta)
# print(c_delta)
if len(c_delta):
    print(n-c_delta.most_common()[0][1])
else:
    print(1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    # test = []
    X, Y = 0, 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            X += v[j]
            Y += c[j]
            # test.append([v[j], c[j]])
    if ans < X - Y:
        ans = X - Y
    # print(test)

print(ans)

Fixed submission:
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    # test = []
    X, Y = 0, 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            X += v[j]
            Y += c[j]
            # test.append([v[j], c[j]])
    if ans < X - Y:
        ans = X - Y
    # print(test)

print(ans)
Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
s = input()
t = [0]*(n + 1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == 'AC' else 0)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - r[l-1])

Fixed submission:
n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
all = s.count('AC')
ans = []
lt = [all]
rt = [all]
# for i in range(n):
#     lt.append(all - s[i:].count('AC'))
#     rt.append(all - s[:n-i].count('AC'))
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        lt.append(lt[i-1] - 1)
    else:
        lt.append(lt[i-1])
    if s[n-i-1] == 'A' and s[n-i] == 'C':
        rt.append(rt[i-1] - 1)
    else:
        rt.append(rt[i-1])

rt.reverse()
# print(lt)
# print(rt)
# print(rt)
for l, r in info:
    ans.append(lt[l-1] + rt[r-1] - all)

for i in range(q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
ans = []
lt = []
rt = []
all = s.count('AC')
for i in range(n):
    lt.append(all - s[i:].count('AC'))
    rt.append(all - s[:n-i].count('AC'))
rt.reverse()
# print(lt)
# print(rt)
for l, r in info:
    ans.append(all - (lt[l-1] + rt[r-1]))

for i in range(q):
    print(ans[i])

Fixed submission:
n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
all = s.count('AC')
ans = []
lt = [all]
rt = [all]
# for i in range(n):
#     lt.append(all - s[i:].count('AC'))
#     rt.append(all - s[:n-i].count('AC'))
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        lt.append(lt[i-1] - 1)
    else:
        lt.append(lt[i-1])
    if s[n-i-1] == 'A' and s[n-i] == 'C':
        rt.append(rt[i-1] - 1)
    else:
        rt.append(rt[i-1])

rt.reverse()
# print(lt)
# print(rt)
# print(rt)
for l, r in info:
    ans.append(lt[l-1] + rt[r-1] - all)

for i in range(q):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
ans = []
for l, r in info:
    ans.append(s[l-1:r].count('AC'))

for i in range(q):
    print(ans[i])

Fixed submission:
n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
all = s.count('AC')
ans = []
lt = [all]
rt = [all]
# for i in range(n):
#     lt.append(all - s[i:].count('AC'))
#     rt.append(all - s[:n-i].count('AC'))
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        lt.append(lt[i-1] - 1)
    else:
        lt.append(lt[i-1])
    if s[n-i-1] == 'A' and s[n-i] == 'C':
        rt.append(rt[i-1] - 1)
    else:
        rt.append(rt[i-1])

rt.reverse()
# print(lt)
# print(rt)
# print(rt)
for l, r in info:
    ans.append(lt[l-1] + rt[r-1] - all)

for i in range(q):
    print(ans[i])