Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

x,y = map(int,input().split())
mod = 10**9+7
if (2*x-y)%3!=0 and (2*y-x)!=0:
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)%mod)*(pow(ka(n),mod-2,mod))%mod
print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9+7
if (x+y)%3!=0:
  print(0)
  exit()
if 2*min(x,y)<max(x,y):
  print(0)
  exit()
n = (2*x-y)//3
m = (2*y-x)//3
#n+mCm
if n==0 or m==0:
  print(1)
  exit()
def ka(x):
  a = 1
  while x!=1:
    a *= x
    x -= 1
    a%= mod
  return a

ans = (ka(n+m)*pow(ka(m),mod-2,mod)%mod)*(pow(ka(n),mod-2,mod))%mod
print(ans)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod = 10**9+7;ans=0
for i in range(60):
  cnt=0
  for a in A: cnt+=a>>i&1
  cnt=cnt*(n-cnt)%mod
  for i in range(i): cnt=cnt*2%mod
  ans+=cnt
print(ans%mod)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod = 10**9+7;ans=0
for i in range(60):
  cnt=sum([1 for a in A if a>>i&1]) 
  cnt=cnt*(n-cnt)%mod
  cnt=2**i*cnt%mod
  ans+=cnt
print(ans%mod)
### BUGGY CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    j = 1 << n - 1
    for i in range(n):
        if X[i] == '0':
            mod = c + 1
            print(f((mp + j % mod) % mod) + 1)
        else:
            print(f((mm - j % mod + mod) % mod) + 1 if (mod := c - 1) != 0 else 0)
        j = j >> 1

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる

from collections import deque

N = int(input())

dist = [[0]*N for _ in range(N)]
neighbor = [[] for _ in range(N)]

for _ in range(N-1):
    u, v, w = map(int, input().split())
    dist[u-1][v-1] = w%2 + 2
    dist[v-1][u-1] = w%2 + 2
    neighbor[u-1].append(v-1)
    neighbor[v-1].append(u-1)

d = deque([0])
color = [0] + [-1]*(N-1)

while color.count(-1) > 0:
    current_point = d.popleft()
    for next_point in neighbor[current_point]:
        if color[next_point] != -1:
            continue
        else:
            color[next_point] = (color[current_point] + dist[current_point][next_point]) % 2
            d.append(next_point)

for idx in range(N):
    print(color[idx])

### FIXED CODE ###

# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる
# 全ての｢辺｣についてループする

from collections import deque

N = int(input())

edge = [[] for _ in range(N)]

for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.pop()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

for idx in range(N):
    print(color[idx])
### BUGGY CODE ###

import itertools

def comb(n, r):
    return len(list(itertools.combinations(range(n), r)))

n = int(input())
s = []
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    s.append(sin)

ss = set(s)
count = 0
for u in ss:
    al = s.count(u)
    count += comb(al, 2)
print(count)

### FIXED CODE ###

import itertools

def comb(n, r):
    return len(list(itertools.combinations(range(n), r)))

def get_runlength(s): # ex) s = 'RRLLLLRLRLRLRR'
    ret = []
    count = 1
    for i in range(len(s)):
        if i == len(s) - 1:
            ret.append((s[i], count))
            continue
        if s[i] == s[i + 1]:
            count += 1
        else:
            ret.append((s[i], count))
            count = 1
    return ret

n = int(input())
dic = {}
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    try:
        dic[sin] += 1
    except:
        dic[sin] = 1

count = 0
for v in dic.values():
    count += v * (v - 1) / 2
count = int(count)
print(count)
### BUGGY CODE ###

def main():
    N, Q = input().split()
    S = input()
    list = []

    for i in range(int(Q)):
        list.append(input().split())

    for i in range(int(Q)):
        sss = S[int(list[i][0]) - 1: int(list[i][1])]
        sss = sss.replace("AC", "1")
        count = sss.count("1")
        print(count)

    return 0


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    list = [0] * (N + 1)

    for i in range(N):
        list[i + 1] = list[i] + (1 if S[i:i + 2] == "AC" else 0)

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
A = [0] * N
for i in range(M):
    for j in range(L[i]-1,R[i]):
        A[j] += 1
        if A[j] == M:
            ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
A = [0] * N
L_max = max(L)
R_min = min(R)
if R_min >= L_max:
    ans = R_min - L_max + 1
else:
    ans = 0
print(ans)
### BUGGY CODE ###

import sys
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (4/N - 1/h - 1/n) == 0: continue
        w = 1 // (4/N - 1/h - 1/n)
        if 0 < w <= 3500 and 4/N == 1/h + 1/n + 1/w:
            print(h, n, int(w))
            sys.exit()


### FIXED CODE ###

import sys

N = int(input())
for h in range(1, 3501):
    for n in range(1, h+1):
        if (4*h*n - N*h - N*n) <= 0:
            continue
        w_int = N*h*n // (4*n*h - N*h - N*n)
        w_float = N*h*n / (4*n*h - N*h - N*n)
        if w_int == w_float:
            print(h, n, w_int)
            sys.exit()
### BUGGY CODE ###

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    alph = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

    pos = np.zeros((26, N), dtype=int)
    for i, c in enumerate(input().strip()):
        p = alph.index(c)
        pos[p][i] = 1

    cur = np.ones(N, dtype=int)
    for _ in range(Q):
        t, d = map(str, input().split())
        p = alph.index(t)
        m = pos[p]
        golem = cur * m

        tmp = golem.tolist()

        if d == 'L':
            tmp.append(0)
            moved_golem = np.array(tmp[1:])
        else:
            tmp = [0] + tmp
            moved_golem = np.array(tmp[:-1])

        cur = cur + moved_golem - golem

    print(np.sum(cur))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(str, input().strip()))
    order = [tuple(map(str, input().split())) for _ in range(Q)]
    order = order[::-1]

    left, right = 0, N-1
    for a in order:
        t, d = a[0], a[1]

        if d == 'L':
            if S[left] == t:
                left += 1
                if left > N - 1:
                    return 0

            if right < N - 1 and S[right + 1] == t:
                right = min(N - 1, right + 1)

        else:
            if left > 0 and S[left - 1] == t:
                left = max(0, left - 1)

            if S[right] == t:
                right -= 1
                if right < 0:
                    return 0

    return right - left + 1


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

tmp = input().split()
K = int(tmp[0])

SGCD = 0

def gcd(a,b,c):
    for ga in range(a+1)[1:]:
        if a % ga == 0:
            Ga = a/ga
            if b % Ga == 0 and c % Ga == 0:
                return Ga
        
        if ga > a/2:
            return 1

for c in range(K+1)[1:]:
    for b in range(c+1)[1:]:
        for a in range(b+1)[1:]:
            if not a == b and not b == c:
                SGCD = SGCD + 6*gcd(a,b,c)
            elif a == b and not b == c:
                SGCD = SGCD + 3*gcd(a,b,c)
            elif not a == b and b == c:
                SGCD = SGCD + 3*gcd(a,b,c)
            elif a == b and b == c:
                SGCD = SGCD + gcd(a,b,c)

print(int(SGCD))

### FIXED CODE ###


import math
from functools import reduce

tmp = input().split()
K = int(tmp[0])

SGCD = 0


def gcd(*numbers):
    return reduce(math.gcd, numbers)

# def gcd(a,b,c):
#     for ga in range(a+1)[1:]:
#         if a % ga == 0:
#             Ga = a/ga
#             if b % Ga == 0 and c % Ga == 0:
#                 return Ga
        
#         if ga > a/2:
#             return 1

for c in range(K+1)[1:]:
    for b in range(c+1)[1:]:
        for a in range(b+1)[1:]:
            if not a == b and not b == c:
                SGCD = SGCD + 6*gcd(a,b,c)
            elif a == b and not b == c:
                SGCD = SGCD + 3*gcd(a,b,c)
            elif not a == b and b == c:
                SGCD = SGCD + 3*gcd(a,b,c)
            elif a == b and b == c:
                SGCD = SGCD + gcd(a,b,c)

print(int(SGCD))
### BUGGY CODE ###

#141D bisect
def main():
    import sys, bisect
    #from collections import deque
    
    N,M =map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A.sort()
    #print(A)
    while M:
        tmp = A.pop()
        bisect.insort(A, tmp//2)
        M-=1
    print(sum(A))
   

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
import heapq
n, m = map(int, sys.stdin.readline().split())
A = list(map(lambda x:-int(x), sys.stdin.readline().split()))
heapq.heapify(A)

for j in range(m):
    heapq.heappush(A ,int(A[0]/2))
    heapq.heappop(A)

print(-sum(A))
### BUGGY CODE ###

from math import gcd

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

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    npcf = False
    for i in range(N - 1):
        for j in range(i + 1, N):
            if gcd(A[i], A[j]) != 1:
                npcf = True
                break
        if npcf:
            break
    
    if not npcf:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from math import gcd

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

prime = list(range(max(A) + 1))

for i in range(2, len(prime)):
    if prime[i] != i:
        continue
    for j in range(i, len(prime), i):
        if prime[j] != j:
            continue
        prime[j] = i

used = set()
pc = True
for a in A:
    used_this = set()
    while a != 1:
        div = prime[a]
        if div in used:
            pc = False
            break
        used_this.add(div)
        a //= div
    used.update(used_this)

if pc:
    print('pairwise coprime')
    exit()

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
exp, max_exp = 0, 0
def calc_exp(p):
  # calculate expectation
  dice = list(range(1, p + 1))
  exp = float(sum(dice) / p)
  return exp
for i in range(N - K + 1):
  k, exp = 0, 0
  while k <= K - 1:
    exp += calc_exp(P[i + k])
    k += 1
  max_exp = max(max_exp, exp)
print(max_exp)

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
acc = [0] + list(accumulate(P))
print((max(b - a for a, b in zip(acc, acc[K:])) + K) / 2)
### BUGGY CODE ###

import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

def dfs(i,j,p,z,w,a,n):
    if p == 0:
        if i == n:
            if j == 0:
                return abs(w - a[-1])
            return abs(a[j -1] - a[-1])
        ans = 0
        for k in range(i,n):
            ans = max(ans,dfs(k + 1,k,1,z,w,a,n))
        if i == 1:
            ans = max(ans,abs(a[-1] - w))
        else:
            ans = max(ans,abs(a[-1]- a[i - 1]))
        return ans
    elif p == 1:
        if i == n:
            if j == 0:
                return abs(z - a[-1])
            return abs(a[j - 1] - a[-1])
        ans = INF
        for k in range(i,n):
            ans = min(ans,dfs(k + 1,k,0,z,w,a,n))
        if i == 1:
            ans = min(ans,abs(a[-1] - z))
        else:
            ans = min(ans,abs(a[-1] - a[i - 1]))
        return ans

def main():
    n,z,w = map(int,input().split())
    a = list(map(int,input().split()))

    ans = dfs(1,0,0,z,w,a,n)
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MAXN = 2005

dp0 = [[-1] * MAXN for _ in range(MAXN)]
dp1 = [[-1] * MAXN for _ in range(MAXN)]

def dfs(i,j,p,z,w,a,n):
    if p == 0:
        if dp0[i][j] != -1:
            return dp0[i][j]
        if i == n:
            if j == 0:
                return abs(w - a[-1])
            return abs(a[j -1] - a[-1])
        ans = 0
        for k in range(i,n):
            ans = max(ans,dfs(k + 1,k,1,z,w,a,n))
        if i == 1:
            ans = max(ans,abs(a[-1] - w))
        else:
            ans = max(ans,abs(a[-1]- a[i - 1]))
        dp0[i][j] = ans
        return ans
    elif p == 1:
        if dp1[i][j] != -1:
            return dp1[i][j]
        if i == n:
            if j == 0:
                return abs(z - a[-1])
            return abs(a[j - 1] - a[-1])
        ans = INF
        for k in range(i,n):
            ans = min(ans,dfs(k + 1,k,0,z,w,a,n))
        if i == 1:
            ans = min(ans,abs(a[-1] - z))
        else:
            ans = min(ans,abs(a[-1] - a[i - 1]))
        dp1[i][j] = ans
        return ans

def main():
    n,z,w = map(int,input().split())
    a = list(map(int,input().split()))

    ans = dfs(1,0,0,z,w,a,n)
    print(ans)

if __name__=='__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
head = True # True: left side is head
for i in range(Q):
  Query_i = list(map(str, input().split()))
  if Query_i[0]=='1':
    head = not head
  elif Query_i[1] == '1' and head:
    S = Query_i[2] + S
  elif Query_i[1] == '1' and not head:
    S = S + Query_i[2]
  elif Query_i[1] == '2' and head:
    S = S + Query_i[2]
  else: # Query_i[1] == '2' and not head:
    S = Query_i[2] + S
if not head:
  S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
flip = False # False: left side is the head
for i in range(Q):
  Query_i = list(map(str, input().split()))
  if Query_i[0]=='1':
    flip = not flip
  elif Query_i[1] == '1' and not flip:
    S.appendleft(Query_i[2])
  elif Query_i[1] == '1' and flip:
    S.append(Query_i[2])
  elif Query_i[1] == '2' and not flip:
    S.append(Query_i[2])
  elif Query_i[1] == '2' and flip:
    S.appendleft(Query_i[2])
if flip:
  S.reverse()
print(''.join(S))
### BUGGY CODE ###

def bellman_ford(v, G, confirm=False):
    ret = [10 ** 10] * len(G)
    ret[v] = 0

    for _ in range(len(G) - 1 if not confirm else (len(G) - 1) * 2):
        for u, g in enumerate(G):
            for w, l in g:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l

    return ret


N, M, P = map(int, input().split())
G = [[] for _ in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    G[A - 1].append((B - 1, - C + P))

ans = bellman_ford(0, G)[-1]
if ans == bellman_ford(0, G, True)[-1]:
    print(max(-ans, 0))
else:
    print('-1')


### FIXED CODE ###

def bellman_ford(v, G):
    import copy
    INF = 10 ** 10
    ret = [INF] * len(G)
    ret[v] = 0

    for _ in range(len(G) - 1):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[u] == INF and ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l

    for _ in range(len(G) - 1):
        for u, g in enumerate(G):
            for w, l in g:
                if not ret[w] == INF and ret[w] > ret[u] + l:
                    ret[w] = -INF

    return ret


N, M, P = map(int, input().split())
G = [[] for _ in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    G[A - 1].append((B - 1, - C + P))

ans = bellman_ford(0, G)[-1]
print("-1" if ans == -10 ** 10 else max(-ans, 0))
### BUGGY CODE ###

from collections import deque

def main():
    q = deque()
    H = 0
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q.append(int(cmd[1]))
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q.popleft()
            H -= 1
            buildMaxHeap(q,H)
        else:
            break

def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            v = A[p-1]
            A[p-1] = A[i-1]
            A[i-1] = v
            increase(A,p)
            
def maxHeapify(A,i,H):
    l = 2*i
    r = 2*i+1
    if l <= H and A[l-1] > A[i-1]:
        largest = l
    else:
        largest = i
    if r <= H and A[r-1] > A[largest-1]:
        largest = r

    if largest != i:
        v = A[i-1]
        A[i-1] = A[largest-1]
        A[largest-1] = v
        maxHeapify(A,largest,H)

def buildMaxHeap(A,H):
    for j in range(H/2):
        i = H/2-j
        maxHeapify(A,i,H)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq

def main():
    q = []
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            heapq.heappush(q,-int(cmd[1]))
        elif cmd[0] == "extract":
            print -heapq.heappop(q)
        else:
            break

if __name__ == "__main__":
    main()
### BUGGY CODE ###

mod=10**9+7
S=list(input())
S.reverse()
a=len(S)
dp=[[0]*13 for _ in range(len(S))]
if S[0]!='?':
    dp[0][int(S[0])]=1
else:
    for l in range(10):
        dp[0][l]=1
for i in range(len(S)-1):
    for j in  range(13):
        if S[i+1]!='?':
            dp[i+1][(j+int(S[i+1])*(10**(i+1)))%13]+=dp[i][j]%mod
        else:
            for k in range(10):
                dp[i+1][(j+k*(10**(i+1)))%13]+=dp[i][j]%mod
print(dp[len(S)-1][5]%mod)

### FIXED CODE ###

mod=10**9+7
S=input()
dp=[0]*13
dp[0]=1

for s in S:
    prev=[x for x in dp]
    dp=[0]*13
    if s=='?':
        nx=range(10)
    else:
        nx=[int(s)]
    for i in range(13):
        for j in nx:
            dp[(10*i+j)%13]+=prev[i]
    dp=[x%mod for x in dp]
print(dp[5])
### BUGGY CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
  for j in range(S+1):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    if j >=A[i]:
      dp[i+1][j] += dp[i][j-A[i]]
      dp[i+1][j] %= mod
print(dp[N][S]%mod)

### FIXED CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
  for j in range(S+1):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    if j + A[i] <=S:
      dp[i+1][j+A[i]] += dp[i][j]
      dp[i+1][j+A[i]] %= mod
print(dp[N][S]%mod)
### BUGGY CODE ###

import sys

def main():
    
    # sys.stdin = open('input_b.txt')

    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] + [float('inf')] * (n - 1)
    
    for i in range(1, n):
        for j in range(max(0, i - k), i):
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))

    print(dp[-1])



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import numpy as np

def main():

    # sys.stdin = open('input_b.txt')
    input = sys.stdin.readline

    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))

    # dp = [0] + [float('inf')] * (n - 1)
    dp = np.zeros(n, dtype=int)
    h = np.array(h)


    for i in range(1, n):
        start = max(0, i-k)
        
        dp[i] = min(dp[start: i] + np.abs(h[i] - h[start : i]))

    print(dp[n-1])



if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
from functools import lru_cache
from itertools import count, takewhile


def prime():
    prime = []

    def _isPrime(n):
        for d in takewhile(lambda x: x * x <= n, prime):
            if n % d == 0:
                return False
        return True
    for i in count(2):
        if _isPrime(i):
            prime.append(i)
            yield(i)


@lru_cache(maxsize=None)
def isPrime(n):
    if n < 2:
        return False
    for p in takewhile(lambda x: x * x <= n, prime()):
        if n % p == 0:
            return False
    return True

n = int(input())
c = 0
for _ in range(n):
    i = int(input())
    if isPrime(i):
        c += 1
print(c)

### FIXED CODE ###

#!/usr/bin/env python3
from itertools import count, takewhile


def prime():
    prime = []

    def _isPrime(n):
        for d in takewhile(lambda x: x * x <= n, prime):
            if n % d == 0:
                return False
        return True
    for i in count(2):
        if _isPrime(i):
            prime.append(i)
            yield(i)


def is_prime(primes, i):
    for p in takewhile(lambda x: x * x <= i, sorted(primes)):
        if i % p == 0:
            return False
    return True

primes = list(takewhile(lambda x: x < 10000, prime()))

n = int(input())
c = 0
for _ in range(n):
    i = int(input())
    if is_prime(primes, i):
        c += 1
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, Q = map(int, input().split())
S = input()
question_list = []

for i in range(Q):
    l, r = map(int, input().split())
    question_list.append((l, r))

cut_s = S
index_list = []
while True:
    index = cut_s.find('AC')
    if index != -1:
        if index_list == []:
            index_list.append(index)
        else:
            index_list.append(index + index_list[-1] + 1)
        cut_s = cut_s[index + 1:]
    else:
        break

for lr in question_list:
    l = lr[0]
    r = lr[1]
    num = 0
    for i in range(l - 1, r - 1):
        if i in index_list:
            num += 1
    print(num)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, Q = map(int, input().split())
S = input()
question_list = []

for i in range(Q):
    l, r = map(int, input().split())
    question_list.append((l, r))

total_list = [0] * N
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        total_list[i + 1] = total_list[i] + 1
    else:
        total_list[i + 1] = total_list[i]

for lr in question_list:
    l = lr[0]
    r = lr[1]
    num = total_list[r - 1] - total_list[l - 1]
    print(num)