Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin
n = (int)(input())
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // math.gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)

Fixed submission:
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin

def gcd(x, y):
	if (y == 0):
		return x
	else:
		return gcd(y, x % y)


n = (int)(input())
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)

Buggy python submission (verdict: Runtime Error):
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin
n = (int)(input())
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // math.gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)

Fixed submission:
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin

def gcd(x, y):
	if (y == 0):
		return x
	else:
		return gcd(y, x % y)


n = (int)(input())
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)

Buggy python submission (verdict: Runtime Error):
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin
n = input()
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // math.gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)

Fixed submission:
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin

def gcd(x, y):
	if (y == 0):
		return x
	else:
		return gcd(y, x % y)


n = (int)(input())
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

M = 0

for i in range(1, N):
    M = M + i

print(M)

Fixed submission:
N = int(input())

s = (N-1) * N // 2
print(s)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def to_dict(s):
    res = defaultdict(int)
    for i in range(0, len(s)):
        c = s[i]
        res[c] = res[c] + 1

    return res

def same_dict(d1, d2):
    for k, v in d1.items():
        if k not in d2:
            return False
        if d1[k] != d2[k]:
            return False

    return True

N = int(input())
s_dicts = []

for i in range(0, N):
    s_dicts.append(to_dict(input()))

count = 0

for i in range(0, N):
    for j in range(i+1, N):
        if same_dict(s_dicts[i], s_dicts[j]):
            count = count + 1

print(count)

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

for i in range(0, N):
    si = input()
    si_sorted = "".join(sorted(list(si)))
    if si_sorted in d:
        d[si_sorted] = d[si_sorted] + 1
    else:
        d[si_sorted] = 1

res = 0
for v in d.values():
    res = res + v * (v - 1) // 2

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
l = input().split(" ")
N = int(l[0])
M = int(l[1])

jobs = []
for i in range(0, N):
    l = input().split(" ")
    jobs.append((int(l[0]), int(l[1])))

jobs.sort(key=lambda x: x[0])
jobs.sort(key=lambda x: x[1], reverse=True)

incomes = 0
for i in range(M-1, -1, -1):
    allowed = M - i
    for j in range(0, len(jobs)):
        if jobs[j][0] <= allowed:
            incomes = incomes + jobs[j][1]
            jobs.pop(j)
            break

print(incomes)

Fixed submission:
from heapq import heappush, heappop

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

works = []
for i in range(0, n):
    a, b = map(int, input().split())
    if a > m:
        continue
    works.append((a, b))

works.sort(reverse=True)

q = []
ans = 0

for i in range(1, m + 1):
    while works and works[-1][0] <= i:
        a, b = works.pop()
        heappush(q, -b)
    if q:
        b = -heappop(q)
        ans += b

print(ans)
Buggy python submission (verdict: Runtime Error):
S, T = input().split()
A, B = map(int, input().split())
U = input()

data = {
    str(S): A,
    str(T): B,
}

data[str(U)] -= 1

s = data[str(S)]
t = data[str(T)]
print(f'{s} {t}')

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

data = {
    str(S): A,
    str(T): B,
}

data[str(U)] -= 1

s = data[str(S)]
t = data[str(T)]
print('{} {}'.format(s, t))

Buggy python submission (verdict: Runtime Error):
S, T = input().split()
A, B = map(int, input().split())
U = input()

data = {
    str(S): A,
    str(T): B,
}

data[f'{U}'] -= 1

s = data[str(S)]
t = data[str(T)]
print(f'{s} {t}')

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

data = {
    str(S): A,
    str(T): B,
}

data[str(U)] -= 1

s = data[str(S)]
t = data[str(T)]
print('{} {}'.format(s, t))
Buggy python submission (verdict: Runtime Error):
N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

dp[0][0][0] = 1

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

dp[0][0][0] = 1

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])

Fixed submission:

# 桁DP問題
N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

dp[0][0][0] = 1

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])
Buggy python submission (verdict: Runtime Error):
# http://drken1215.hatenablog.com/entry/2020/01/26/225000

H, N = map(int, input().split())
dp = [float("inf") for i in range(H+1)]

dp[0] = 0

for i in range(N):
  a, b = map(int, input().split())
  
  for j in range(H):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


print(dp[H])

Fixed submission:


H, A = map(int, input().split())


ans = 0
while H > 0:
  ans += 1
  H -= A

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# http://drken1215.hatenablog.com/entry/2020/01/26/225000

H, N = map(int, input().split())
dp = [float("inf") for i in range(H+1)]

dp[0] = 0

for i in range(N):
  a, b = map(int, input().split())
  
  for j in range(H):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


print(dp[H])

Fixed submission:
H, N = map(int, input().split())
dp = [10**8 for i in range(H+1)]

dp[0] = 0

for i in range(N):
  a, b = map(int, input().split())
  
  for j in range(H):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


print(dp[H])
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

count = 0
result = []

def get(x):
  if x == "r":
    return ("p", P)
  elif x == "s":
    return ("r", R)
  elif x == "p":
    return ("s", S)


for i in range(N):
  x = T[i]
  hand, point = get(x)
  if i < K:
    # 前回の結果は気にしなくても良いとき
    result.append((hand, point))
  elif hand != result[i-K][0]:
    result.append((hand, point))
  else:
    if i + K >= N:
      # 後のことを考えなくて良いとき
      result.append((hand, 0))
    else:
      next = list(filter(lambda x: x not in (T[i+2], hand), ["r", "s", "p"]))[0]
      result.append((next, 0))

print(sum(list(map(lambda x: x[1], result))))



Fixed submission:



N, K = map(int,input().split())
R, S, P = map(int, input().split())
T = input()

point = 0

judge = {"r": R, "s": S, "p": P}
skip = [False] * N

for i in range(N):
  if i < K:
    if T[i] == "r":
      point += judge["p"]
    elif T[i] == "s":
      point += judge["r"]
    elif T[i] == "p":
      point += judge["s"]
  else:
    # K回前を意識しないといけない
    if T[i-K] != T[i] or skip[i-K]:
      if T[i] == "r":
        point += judge["p"]
      elif T[i] == "s":
        point += judge["r"]
      elif T[i] == "p":
        point += judge["s"]
    else:
      skip[i] = True
      
print(point)
Buggy python submission (verdict: Time Limit Exceeded):

# グラフ問題での分析が全然できなかった（初体験）
# 次回は頑張って解く！

N, u, v = map(int, input().split())
edges = [[] for i in range(N+1)]

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

def dfs(u):
  colors = ["white"] * (N+1)
  d = [None] * (N + 1)
  d[u] = 0
  stack = [u]

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for e in edges[u]:
      if colors[e] != "black":
        d[e] = d[u] + 1
        stack.append(e)

  return d

u_dist = dfs(u)
v_dist = dfs(v)

ans = 0
for uu in u_dist:
  if uu == None: continue
  for vv in v_dist:
    if vv == None: continue
    if uu < vv:
      ans = max(ans, vv - 1)

print(ans)

Fixed submission:

# グラフ問題での分析が全然できなかった（初体験）
# 次回は頑張って解く！
# 解説動画をみることがMUST、基本そのまま書いている。

from heapq import heappop, heappush
N, u, v = map(int, input().split())
edges = [[] for i in range(N+1)]

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

def dfs(u):
  colors = ["white"] * (N+1)
  d = [9999999999999999] * (N + 1)
  d[u] = 0
  stack = [u]

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for e in edges[u]:
      if colors[e] != "black":
        d[e] = d[u] + 1
        stack.append(e)

  return d

u_dist = dfs(u)
v_dist = dfs(v)

ans = 0
for i in range(N+1):
  if u_dist[i] < v_dist[i]:
    ans = max(ans, v_dist[i] - 1)

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

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


ans = 0

for i in range(61):

  one = 0
  for a in A:
    if (a >> i) & 1:
      one += 1
  
  zero = N - one
  ans += one * zero * (2 ** i)
  ans %= mod

print(ans)

Fixed submission:

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


ans = 0

for i in range(61):

  one = 0
  for a in A:
    if (a >> i) & 1:
      one += 1
  
  zero = N - one
  ans += one * zero * (2 ** i)
  ans %= mod

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

A, B = map(int, input().split())

from fractions import gcd
import math
from collections import Counter
from itertools import combinations

def trial_division(n):
    if n == 1: return []
    
    result = []
    
    for k in range(2, n):
      while n % k == 0:
        n //= k
        result.append(k)

    if not result:
      result.append(n)
      return result
    else:
      return result

G = gcd(A, B)
if G == 1:
  print(1)
  exit()

D = [1] + list(Counter(trial_division(G)).keys())
print(len(D))

Fixed submission:

A, B = map(int, input().split())

from fractions import gcd
import math
from collections import Counter
from itertools import combinations

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

G = gcd(A, B)
if G == 1:
  print(1)
  exit()

D = [1] + list(Counter(prime_factorize(G)).keys())
print(len(D))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
for i in range(1, n):
  if a[i] == a[i - 1] + 1 and i != n:
    ans += c[a[i] - 1]

print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
for i in range(1, n):
  if a[i] == a[i - 1] + 1:
    ans += c[a[i - 1] - 1]

print(ans)
Buggy python submission (verdict: Runtime Error):

N = int(input())
L = list(range(1, N))

from functools import reduce
from operator import add

if N == 1:
  print(0)
  exit()

print(reduce(add, L))

Fixed submission:
N = int(input())

print((N) * (N-1) // 2)

Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())

ans = 0
for i in range(1, N):
  ans += i % (i+1)

print(ans)

Fixed submission:
N = int(input())

print((N) * (N-1) // 2)

Buggy python submission (verdict: Runtime Error):

N = int(input())

X = list(range(1, N+1))
Y = X[:]
Y.append(Y.pop(0))

ans = 0
for i in range(N):
  ans += X[i] % Y[i]

print(ans)

Fixed submission:
N = int(input())

print((N) * (N-1) // 2)
Buggy python submission (verdict: Runtime Error):
a = input()
s = input()
print(s if a >= 3200 else "red")

Fixed submission:
a = int(input())
s = input()
print(s if a >= 3200 else "red")
Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())
A = list(map(int, input().split()))[::-1]

ans = []

for i in range(N):
  j = N - i
  cnt = 0 

  for m in [n for n in range(j, N+1) if (n % j == 0) and (n != j) ]:
    cnt += A[N - m]
  
  if (cnt + A[i]) % 2 == 1:
    ans.append(j)

len_ans = len(ans)
if len_ans == 0:
  print(0)
else:
  print(len_ans)
  print(*ans[::-1])

Fixed submission:

N = int(input())
A = list(map(int, input().split()))
B = set()

for i in list(range(1, N+1))[::-1]:
  tmp = i
  cnt = 0
  while tmp <= N:
    if tmp in B:
      cnt += 1    
    tmp += i

  if cnt % 2 != A[i-1]:
    B.add(i)

len_b = len(B)
if len_b == 0:
  print(0)
else:
  print(len_b)
  print(*sorted(list(B)))

Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())
A = list(map(int, input().split()))[::-1]

ans = []

for i in range(N):
  j = N - i
  cnt = 0 

  for m in [n for n in range(1, N+1) if (n % j == 0) and (n != j) ]:
    cnt += A[N - m]
  
  if (cnt + A[i]) % 2 == 1:
    ans.append(j)

len_ans = len(ans)
if len_ans == 0:
  print(0)
else:
  print(len_ans)
  print(*ans)

Fixed submission:

N = int(input())
A = list(map(int, input().split()))
B = set()

for i in list(range(1, N+1))[::-1]:
  tmp = i
  cnt = 0
  while tmp <= N:
    if tmp in B:
      cnt += 1    
    tmp += i

  if cnt % 2 != A[i-1]:
    B.add(i)

len_b = len(B)
if len_b == 0:
  print(0)
else:
  print(len_b)
  print(*sorted(list(B)))
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
from heapq import heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

BC = []

for i in range(M):
  b, c = map(int, input().split())
  heappush(BC, (-c, b))

for i in range(M):
  mc, b = heappop(BC)
  c = -mc
  index = bisect_left(A, c)

  if index == 0:
    continue
  
  if index <= b:
    A = [c for _ in range(index) ] + A[index:]
  else:
    A = [c for _ in range(b)] + A[b:]
  
  A.sort()

print(sum(A))

Fixed submission:
from heapq import heappop, heappush, heapify

N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
BC = []

for i in range(M):
  b, c = map(int, input().split())
  heappush(BC, (-c, b))

for i in range(M):
  mc, b = heappop(BC)
  c = -mc
  end = False

  for j in range(b):
    min = heappop(A)
    if c <= min:
      heappush(A, min)
      end = True
      break
    else:
      heappush(A, c)

  if end:
    break

print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

for i in range(M):
  b, c = map(int, input().split())
  index = bisect_left(A, c)
  
  if index <= b:
    A = [c for _ in range(index) ] + A[index:]
  else:
    A = [c for _ in range(b)] + A[b:]
  
  A.sort()

print(sum(A))

Fixed submission:
from heapq import heappop, heappush, heapify

N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
BC = []

for i in range(M):
  b, c = map(int, input().split())
  heappush(BC, (-c, b))

for i in range(M):
  mc, b = heappop(BC)
  c = -mc
  end = False

  for j in range(b):
    min = heappop(A)
    if c <= min:
      heappush(A, min)
      end = True
      break
    else:
      heappush(A, c)

  if end:
    break

print(sum(A))
Buggy python submission (verdict: Runtime Error):


from math import gcd
from functools import reduce # reduceの使い方覚える、ついでにaccumulateも

def divider(numbers):
  return reduce(gcd, numbers)

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

result = []
for i in range(n):
  numbers = A[:]
  numbers.pop(i)
  result.append(divider(numbers))
print(max(result))

Fixed submission:
a, b, t = map(int, input().split())
print(int((t + 0.5) / a) * b)
Buggy python submission (verdict: Time Limit Exceeded):

from fractions import gcd
from functools import reduce

N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(N):
 B = A[:]
 B.pop(i)
 ans = max(ans, reduce(gcd, B))

print(ans)

Fixed submission:
# 参考1: https://atcoder.jp/contests/abc125/submissions/8965716
# 参考2: https://qiita.com/hkrutknouch/items/e71488de4a0c8e83ee97

from fractions import gcd
from itertools import accumulate

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

left = list(accumulate(A, gcd))
right = list(accumulate(A[::-1], gcd))[::-1]

ans = 0
for i in range(n):
  if i == 0:
    tmp = right[1]
  elif i == n - 1:
    tmp = left[-2]
  else:
    tmp = gcd(left[i-1], right[i+1])
  ans = max(ans, tmp)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):


from fractions import gcd
from functools import reduce # reduceの使い方覚える、ついでにaccumulateも

def divider(numbers):
  return reduce(gcd, numbers)

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

result = []
for i in range(n):
  numbers = A[:]
  numbers.pop(i)
  result.append(divider(numbers))
print(max(result))

Fixed submission:
# 参考1: https://atcoder.jp/contests/abc125/submissions/8965716
# 参考2: https://qiita.com/hkrutknouch/items/e71488de4a0c8e83ee97

from fractions import gcd
from itertools import accumulate

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

left = list(accumulate(A, gcd))
right = list(accumulate(A[::-1], gcd))[::-1]

ans = 0
for i in range(n):
  if i == 0:
    tmp = right[1]
  elif i == n - 1:
    tmp = left[-2]
  else:
    tmp = gcd(left[i-1], right[i+1])
  ans = max(ans, tmp)

print(ans)

Buggy python submission (verdict: Runtime Error):


from math import gcd
from functools import reduce # reduceの使い方覚える、ついでにaccumulateも

def divider(numbers):
  return reduce(gcd, numbers)

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

result = []
for i in range(n):
  numbers = A[:]
  numbers.pop(i)
  result.append(divider(numbers))
print(max(result))

Fixed submission:
# 参考1: https://atcoder.jp/contests/abc125/submissions/8965716
# 参考2: https://qiita.com/hkrutknouch/items/e71488de4a0c8e83ee97

from fractions import gcd
from itertools import accumulate

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

left = list(accumulate(A, gcd))
right = list(accumulate(A[::-1], gcd))[::-1]

ans = 0
for i in range(n):
  if i == 0:
    tmp = right[1]
  elif i == n - 1:
    tmp = left[-2]
  else:
    tmp = gcd(left[i-1], right[i+1])
  ans = max(ans, tmp)

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


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

for q in range(Q):
  s, t = map(int, input().split())
  print(S[s-1:t:1].count("AC"))

Fixed submission:

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

A = []

for n in range(N):
  if n == 0:
    A.append(0)
  elif S[n] == "C" and S[n-1] == "A":
    A.append(A[n-1] + 1)
  else:
    A.append(A[n-1])

A.insert(0, 0)

for i in range(Q):
  x, y = map(int, input().split())
  print(A[y] - A[x])

Buggy python submission (verdict: Time Limit Exceeded):

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

for i in range(Q):
  f, t = map(int, input().split())
  print(S[f-1:t].count("AC"))

Fixed submission:

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

A = []

for n in range(N):
  if n == 0:
    A.append(0)
  elif S[n] == "C" and S[n-1] == "A":
    A.append(A[n-1] + 1)
  else:
    A.append(A[n-1])

A.insert(0, 0)

for i in range(Q):
  x, y = map(int, input().split())
  print(A[y] - A[x])
Buggy python submission (verdict: Runtime Error):

from functools import reduce

A, B = map(int, input().split())

def xor(x, y):
  return x ^ y

print(reduce(xor, list(range(A, B+1))))

Fixed submission:

# XORの性質を覚える必要がある
# 解説動画を"最後まで"みるとわかりやすい

from functools import reduce

A, B = map(int, input().split())

def get(x):
  # 何かしらの法則をみつける
  return [x, 1, x + 1, 0][x % 4]

# XORの性質
print( get(B) ^ get(A - 1) )
Buggy python submission (verdict: Time Limit Exceeded):

N, M = map(int, input().split())
adj = [[] for i in range(N)]
ng = [[] for i in range(N)]

ninp = []

for i in range(M):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  adj[x].append(y)
  adj[y].append(x)
  ninp.append((x, y))

def search():
  edges = [[None for i in range(N)] for j in range(N)]

  def dfs(u, f):
    stack = [u]
    colors = ["white"] * N

    while stack:
      u = stack.pop()
      colors[u] = "black"
      edges[f][u] = 0

      for v in list(filter(lambda x: colors[x] != "black" and not x in ng[u], adj[u])):
        stack.append(v)
        colors[v] = "gray"

  for u in range(N):
    dfs(u, u)

  ans = 0
  
  for n in range(N):
    for m in range(n, N):
      if edges[n][m] == None:
        ans += 1
  print(ans)

for (x, y) in ninp:
  ng[x].append(y)
  ng[y].append(x)
  search()



Fixed submission:
# TLEしない適切な解法を思いつけず

class UnionFind:

  def __init__(self, n):
    self.parents = [-1] * n

  def find(self, n):
    if self.parents[n] < 0:
      return n

    self.parents[n] = self.find(self.parents[n])
    return self.parents[n]

  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 is_same(self, x, y):
    x = self.find(x)
    y = self.find(y)
    return x == y


N, M = map(int, input().split())
edges = []

for i in range(M):
  x, y = map(int, input().split())
  edges.append((x,y))

uf = UnionFind(N)

ans = [N * (N-1) // 2]

for i in range(M-1, 0, -1):
  x, y = edges[i]
  x -= 1
  y -= 1
  if not uf.is_same(x, y):
    ans.append(ans[-1] - uf.size(x) * uf.size(y))
    uf.union(x, y)
  else:
    ans.append(ans[-1])
    
for a in ans[::-1]:
  print(a)