Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7
N, M = [int(_) for _ in input().split()]

factorize_result = {}
def factorization(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            factorize_result[i] = 1
            n = n // i
            while n % i == 0:
                factorize_result[i] += 1
                n = n // i
    if n > 1:
        factorize_result[n] = 1


factorial = [1] * (2 * N)
def calc_factorial():
    for i in range(1, 2 * N):
        factorial[i] = i * factorial[i - 1] % mod


def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 素因数分解
factorization(M)

# 階乗を用意
calc_factorial()

ans = 1
for k, v in factorize_result.items():
    ans *= comb(N + v - 1, v) % mod

print(ans % mod)


Fixed submission:
mod = 10 ** 9 + 7
N, M = [int(_) for _ in input().split()]

MAX_N = 10 ** 5 + 100

factorize_result = {}
def factorization(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            factorize_result[i] = 1
            n = n // i
            while n % i == 0:
                factorize_result[i] += 1
                n = n // i
    if n > 1:
        factorize_result[n] = 1


factorial = [1] * MAX_N
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod


def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 素因数分解
factorization(M)

# 階乗を用意
calc_factorial()

ans = 1
for k, v in factorize_result.items():
    ans *= comb(N + v - 1, v) % mod

print(ans % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
s = S[:]
while '()' in s:
    s.replace('()', '')
ans = '(' * s.count(')') + S + ')' * s.count('(')
print(ans)


Fixed submission:
N = int(input())
S = input()
s = S[:]
while '()' in s:
    s = s.replace('()', '')
ans = '(' * s.count(')') + S + ')' * s.count('(')
print(ans)
Buggy python submission (verdict: Runtime Error):

N, A = [int(_) for _ in input().split()]
x = sorted([int(_) for _ in input().split()])

dp = [[0] * (sum(x)+1) for j in range(N+1)]

dp[0][0] = 1
for i in range(1, N+1):
    for j in list(range(1, N+1))[::-1]:
        for k in list(range(x[i-1], sum(x[:i])+1))[::-1]:
            dp[j][k] += dp[j-1][k - x[i-1]]

print(sum([dp[i][i*A] for i in range(1, N+1)]))


Fixed submission:

N, A = [int(_) for _ in input().split()]
x = sorted([int(_) for _ in input().split()])

dp = [[0] * (sum(x)+1) for j in range(N+1)]

dp[0][0] = 1
for i in range(1, N+1):
    for j in list(range(1, N+1))[::-1]:
        for k in list(range(x[i-1], sum(x[:i])+1))[::-1]:
            dp[j][k] += dp[j-1][k - x[i-1]]

print(sum([dp[i][i*A] for i in range(1, N+1) if i*A <= sum(x)]))
Buggy python submission (verdict: Runtime Error):

import math

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n%b

if n == s:
    print(n+1)
    exit()

for b in range(2, int(math.sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        exit()

for p in list(range(1, min(int(math.sqrt(n))+1, s+1)))[::-1]:
    q = s - p
    b = (n - q) // p
    if f(b, n) == s:
        print(b)
        exit()

print(-1)

Fixed submission:

import math

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n%b

if n == s:
    print(n+1)
    exit()

for b in range(2, int(math.sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        exit()

for p in list(range(1, min(int(math.sqrt(n))+1, s+1)))[::-1]:
    q = s - p
    b = (n - q) // p
    if b >= 2 and f(b, n) == s:
        print(b)
        exit()

print(-1)

Buggy python submission (verdict: Runtime Error):

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n%b


for b in range(int(math.sqrt(n))):
    if f(b, n) == s:
        print(b)
        exit()

for p in range(int(math.sqrt(n))):
    q = s - p
    b = (n - q) // p
    if f(b, n) == s:
        print(b)
        exit()
        
print(-1)

Fixed submission:

import math

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n%b

if n == s:
    print(n+1)
    exit()

for b in range(2, int(math.sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        exit()

for p in list(range(1, min(int(math.sqrt(n))+1, s+1)))[::-1]:
    q = s - p
    b = (n - q) // p
    if b >= 2 and f(b, n) == s:
        print(b)
        exit()

print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10 ** 9 + 7
n = int(input())
l = len(input())
dp = [[0] * (n + 2) for j in range(n + 1)]

for i in range(n + 1):
    for j in range(i + 1):
        if i == 0:
            dp[i][j] = 1
        elif j == 0:
            dp[i][j] = (dp[i - 1][1] * 2 + dp[i - 1][0]) % mod
        else:
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1] * 2) % mod

print(dp[n][l])


Fixed submission:
mod = 10 ** 9 + 7
n = int(input())
l = len(input())
dp = [[0] * (n + 2) for j in range(n + 1)]

for i in range(n + 1):
    for j in range(i + 1):
        if i == 0:
            dp[i][j] = 1
        elif j == 0:
            dp[i][j] = (dp[i - 1][1] * 2 + dp[i - 1][0]) % mod
        else:
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1] * 2) % mod

print(dp[n][l])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    P = [list(map(int, input().split())) for _ in range(n)]
    ans = 0

    for i, pi in enumerate(P):
        for pj in P[i+1:]:
            ans = max(ans, abs(pi[0] - pj[0])+abs(pi[1] - pj[1]))

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    P = [list(map(int, input().split())) for _ in range(n)]
    C0, C1 = [], []
    ans = 0

    for pi in P:
        C0.append(pi[0] - pi[1])
        C1.append(pi[0] + pi[1])

    C0min = min(C0)
    C0max = max(C0)
    C1min = min(C1)
    C1max = max(C1)

    print(max(C0max - C0min, C1max - C1min))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)

    for _ in range(m):
        a, b = map(int, input().split())
        uf.union(a-1, b-1)
    
    print(len(max(uf.all_group_members().values(), key=lambda x: len(x))))


if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque


def main():
    n, m = map(int, input().split())
    is_checked = [False for _ in range(n+1)]
    edges = [[] for _ in range(n+1)]
    ans = 0

    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

    for ni in range(n):
        if is_checked[ni]:
            continue
        is_checked[ni] = True
        q = deque([ni])
        depth = 0
        while len(q) > 0:
            p = q.popleft()
            for e in edges[p]:
                if not is_checked[e]:
                    is_checked[e] = True
                    q.append(e)
            depth += 1

        ans = max(ans, depth)

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def main():
    h, w = map(int, input().split())
    cs = list(map(int, input().split()))
    ds = list(map(int, input().split()))
    S = [[s for s in input()] for _ in range(h)]

    curq = deque()
    nexq = deque([(cs[0] - 1, cs[1] - 1)])
    l = 0
    while len(nexq) > 0:
        curq, nexq = nexq, deque()
        while len(curq) > 0:
            y, x = curq.popleft()
            if S[y][x] != ".":
                continue

            S[y][x] = l
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    if 0 <= y + dy < h and 0 <= x + dx < w and S[y + dy][x + dx] == ".":
                        if abs(dx) + abs(dy) < 2:
                            curq.append((y + dy, x + dx))
                        else:
                            nexq.append((y + dy, x + dx))
        l += 1

    ans = S[ds[0] - 1][ds[1] - 1]
    print(ans if ans != "." else -1)


if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque


def main():
    h, w = map(int, input().split())
    cs = list(map(int, input().split()))
    ds = list(map(int, input().split()))
    S = [[s for s in input()] for _ in range(h)]

    curq = deque()
    nexq = deque([(cs[0] - 1, cs[1] - 1)])
    l = 0
    while len(nexq) > 0:
        curq, nexq = nexq, deque()
        while len(curq) > 0:
            y, x = curq.popleft()
            if S[y][x] != ".":
                continue

            S[y][x] = l
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    if 0 <= y + dy < h and 0 <= x + dx < w and S[y + dy][x + dx] == ".":
                        if abs(dx) + abs(dy) < 2:
                            curq.append((y + dy, x + dx))
                        else:
                            nexq.append((y + dy, x + dx))
        l += 1

    ans = S[ds[0] - 1][ds[1] - 1]
    print(ans if ans != "." else -1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = input()
    return N % 1000


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    if N % 1000 == 0:
        print(0)
    else:
        print(1000 - (N % 1000))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input(): return sys.stdin.readline().strip()


def main():
    N, M, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]

    a, b = [0], [0]
    for i in range(N):
        a.append(sum(A[:i+1]))

    for i in range(M):
        b.append(sum(B[:i+1]))

    ans, j = 0, M
    for i in range(len(a)):
        if a[i] > K:
            break
        while a[i] + b[j] > K:
            j -= 1
        ans = max(ans, i + j)

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input(): return sys.stdin.readline().strip()


def main():
    N, M, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]

    a, b = [0], [0]
    for i in range(N):
        a.append(a[i] + A[i])

    for i in range(M):
        b.append(b[i] + B[i])

    ans, j = 0, M
    for i in range(len(a)):
        if a[i] > K:
            break
        while a[i] + b[j] > K:
            j -= 1
        ans = max(ans, i + j)

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    n = int(input())
    As = list(map(int, input().split()))
    ans = 1

    for a in As:
        ans *= a

    if ans > 10**18:
        print(-1)
        return
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:

def main():
    n = int(input())
    As = list(map(int, input().split()))
    ans = 1
    if 0 in As:
        print(0)
        return

    for a in As:
        ans *= a
        if ans > 10**18:
            print(-1)
            return

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input()
    if n < 4:
        print(0)
        return
    ans = 0

    for i, si in enumerate(s[:-2]):
        for j, sj in enumerate(s[i+1:-1]):
            if si == sj:
                continue
            for k, sk in enumerate(s[i+j+2:]):
                if j == k:
                    continue
                if si != sk != sj:
                    ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n = int(input())
    s = input()
    if n < 4:
        print(0)
        return
    ans = s.count("R") * s.count("G") * s.count("B")

    for i, si in enumerate(s[:-2]):
        for j, sj in enumerate(s[i+1:-1]):
            if si == sj:
                continue

            if i + 2*j+2 < n and si != s[i + 2*j+2] != sj:
                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    s_array = [''.join(sorted(input()[:-1])) for _ in range(n)]

    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if(s_array[i] == s_array[j]):
                count += 1

    print(count)


Fixed submission:
import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    s_array = [''.join(sorted(input()[:-1])) for _ in range(n)]

    s_array.sort()
    ans = 0
    count = 0
    word = s_array[0]
    for i in range(1, n):
        if(word == s_array[i]):
            count += 1
        else:
            ans += (count*(count+1))//2
            count = 0
        word = s_array[i]

    ans += (count*(count+1))//2
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    s_array = [sorted(input()[:-1]) for _ in range(n)]

    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if(s_array[i] == s_array[j]):
                count += 1

    print(count)


Fixed submission:
import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    s_array = [''.join(sorted(input()[:-1])) for _ in range(n)]

    s_array.sort()
    ans = 0
    count = 0
    word = s_array[0]
    for i in range(1, n):
        if(word == s_array[i]):
            count += 1
        else:
            ans += (count*(count+1))//2
            count = 0
        word = s_array[i]

    ans += (count*(count+1))//2
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def main(n, s_array):
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if(s_array[i] == s_array[j]):
                count += 1
    return count


if __name__ == "__main__":
    n = int(input())
    s_array = [sorted(input()[:-1]) for _ in range(n)]

    print(main(n, s_array))


Fixed submission:
import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    s_array = [''.join(sorted(input()[:-1])) for _ in range(n)]

    s_array.sort()
    ans = 0
    count = 0
    word = s_array[0]
    for i in range(1, n):
        if(word == s_array[i]):
            count += 1
        else:
            ans += (count*(count+1))//2
            count = 0
        word = s_array[i]

    ans += (count*(count+1))//2
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(min(r-l-c, 2019)):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    break
        c += 1

    print(mi)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(min(r-l-c, 2019)):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    print(0)
                    return 
        c += 1

    print(mi)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(r-l-c):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    break
        c += 1

    print(mi)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(min(r-l-c, 2019)):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    print(0)
                    return 
        c += 1

    print(mi)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(r-l-c):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    break
        c += 1

    print(mi)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    l, r = map(int, input().split())
    mi = 2019
    c = 0

    for i in range(l, r):
        a = (i*i) % 2019
        for _ in range(min(r-l-c, 2019)):
            a = (a+i) % 2019

            if a < mi:
                mi = a
                if a == 0:
                    print(0)
                    return 
        c += 1

    print(mi)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
restourants = dict()

for i in range(N):
    S, P = map(str,input().split())
    if S not in restourants:
        restourants[S] = {}
    restourants[S][int(P)] = i+1
for k, v in sorted(restourants.items()):
    if len(v)>1:
        v = sorted(v.items(),reverse=True)
  
    
    for i in v:
        print(i[1])

Fixed submission:
N = int(input())
restourants = dict()

for i in range(N):
    S, P = map(str,input().split())
    if S not in restourants:
        restourants[S] = {}
    restourants[S][int(P)] = i+1
for k, v in sorted(restourants.items()):
    v = sorted(v.items(),reverse=True)
    for i in v:
        print(i[1])

Buggy python submission (verdict: Runtime Error):
N = int(input())
restourants = dict()

for i in range(N):
    S, P = map(str,input().split())
    if S not in restourants:
        restourants[S] = {}
    restourants[S][int(P)] = i+1
for k, v in sorted(restourants.items()):
    if len(v)>1:
        v = sorted(v.items(),reverse=True)
    
    for i in v:
        print(i[1])

Fixed submission:
N = int(input())
restourants = dict()

for i in range(N):
    S, P = map(str,input().split())
    if S not in restourants:
        restourants[S] = {}
    restourants[S][int(P)] = i+1
for k, v in sorted(restourants.items()):
    v = sorted(v.items(),reverse=True)
    for i in v:
        print(i[1])
Buggy python submission (verdict: Runtime Error):
N, M = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(M):
    B, C = map(int,input().split())
    A += [C]*B
    A.sort(reverse=True)
    A = A[:N]
print(sum(A))

Fixed submission:
A ,B = map(int,input().split())

if 13 <= A:
    print(B)
elif 6 <= A:
    print(B//2)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
a = [0]*5
for i in range(5):
  a[i] = input()
k = input()
if (max(a)-min(a))>k:
  print(':(')
else:
  print('Yay!')

Fixed submission:
a = [0]*5
for i in range(5):
  a[i] = int(input())
k = int(input())
if (max(a)-min(a))>k:
  print(':(')
else:
  print('Yay!')
Buggy python submission (verdict: Runtime Error):
A,B,C = map(int,input().split())
if (A==B)and(B==C):
  print"Yes"
else:
  print"No"

Fixed submission:
A,B,C = map(int,input().split())
if (A==B)and(B==C):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
i = input()
if i == 'A':
  print('T')
else if i == 'T':
  print('A')
else if i == 'C':
  print('G')
else if i == 'G':
  print('C')

Fixed submission:
i = input()
if i == 'A':
  print('T')
elif i == 'T':
  print('A')
elif i == 'C':
  print('G')
elif i == 'G':
  print('C')

Buggy python submission (verdict: Runtime Error):
def func():
	i = input()
	if i == 'A':
    	return 'T'
    else if i == 'T':
    	return 'A'
    else if i == 'C':
    	return 'G'
    else if i == 'G':
    	return 'C'

print(func())
  

Fixed submission:
i = input()
if i == 'A':
  print('T')
elif i == 'T':
  print('A')
elif i == 'C':
  print('G')
elif i == 'G':
  print('C')
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(n-1):
    if (S[i]=='A')and(S[i+1]=='C'):
        a[i] = 1

for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for k in range(l-1,r-1):
        ans += a[k]
    print(ans)


Fixed submission:
n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(1,n):
    a[i] = a[i-1]
    if (S[i-1]=='A')and(S[i]=='C'):
        a[i] += 1 
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
S = list(input())
l = [0]*q
r = [0]*q
for i in range(q):
    l,r = map(int,input().split())
    count = 0
    for i in range(l-1,r-1): #最後にAが出ても意味ないのでr-1でカット
        if(S[i]=='A'):
            if(S[i+1]=='C'):
                count += 1
    print(count)


Fixed submission:
n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(1,n):
    a[i] = a[i-1]
    if (S[i-1]=='A')and(S[i]=='C'):
        a[i] += 1 
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
def ACcount(l,r):
    count = 0
    for i in range(l-1,r-1): #最後にAが出ても意味ないのでr-1でカット
        if(S[i]=='A'):
            if(S[i+1]=='C'):
                count += 1
    return count

n,q = map(int,input().split())
S = list(input())
l = [0]*q
r = [0]*q
for i in range(q):
    l,r = map(int,input().split())
    print(ACcount(l,r))
"""
for i in range(q):
    l[i],r[i] = map(int,input().split())

for i in range(q):
    print(ACcount(l[i],r[i]))
"""

Fixed submission:
n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(1,n):
    a[i] = a[i-1]
    if (S[i-1]=='A')and(S[i]=='C'):
        a[i] += 1 
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
def ACcount(l,r):
    count = 0
    for i in range(l-1,r-1): #最後にAが出ても意味ないのでr-1でカット
        if(S[i]=='A'):
            if(S[i+1]=='C'):
                count += 1
    return count

n,q = map(int,input().split())
S = list(input())
l = [0]*q
r = [0]*q
for i in range(q):
    l[i],r[i] = map(int,input().split())

for i in range(q):
    print(ACcount(l[i],r[i]))


Fixed submission:
n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(1,n):
    a[i] = a[i-1]
    if (S[i-1]=='A')and(S[i]=='C'):
        a[i] += 1 
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])