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

n, m = map(int,input().split())
plst = list(map(int,input().split()))
pare_inds = [i for i in range(n)]
belongs = [[] for i in range(n)]

def get_root(x):
  p = pare_inds[x]
  if p == x:
    return x
  a = get_root(p)
  pare_inds[x] = a
  return a
#def get_root(x):
#  lst = []
#  while pare_inds[x] != x:
#    lst.append(x)
#    x = pare_inds[x]
#  for i in lst:
#    pare_inds[i] = x
#  return x
#
for i in range(m):
  x, y = map(int,input().split())
  x, y = x - 1, y - 1
  r_x, r_y  = get_root(x), get_root(y)
  if r_x < r_y:
    pare_inds[y] = r_x
    pare_inds[r_y] = r_x
  elif r_x > r_y:
    pare_inds[x] = r_y
    pare_inds[r_x] = r_y
#  print(x,y,p_x,p_y,pare_inds)

for i in range(n):
  belongs[get_root(i)].append(i)

ans = 0
for lst in belongs:
  for i in lst:
    if plst[i] - 1 in lst:
      ans += 1

print(ans)
#print(belongs)
#print(pare_inds)

### FIXED CODE ###

def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)
  #print(belongs)
  #print(plst)
  ans = 0
  for lst in belongs:
    lst2 = [plst[i] - 1 for i in lst]
    lst.sort()
    lst2.sort()
    ind1 = 0
    ind2 = 0
    end = len(lst)
    while ind1 < end and ind2 < end:
      if lst[ind1] == lst2[ind2]:
        ans += 1
        ind1 += 1
        ind2 += 1
      elif lst[ind1] < lst2[ind2]:
        ind1 += 1
      else:
        ind2 += 1
  
  print(ans)
solve()
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
x = [False]*(n)
ans = 0
for i in range(n):
    if x[i] == False:
        ans += 1
        x[i] = True
    for j in range(i+1,n):
        if a[i] < a[j] and x[j] == False:
            x[j] = True

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
m = []
for i in range(n):
    r = bisect.bisect_right(m,-a[i])
    if r == len(m):
        m.append(-a[i])
    else:
        m[r] = -a[i]
print(len(m))
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
b = np.zeros(n)
for i in range(1,n):
    b[i-1] = a.count(i)
    print(int(b[i-1]))
print(int(b[n-1]))


### FIXED CODE ###

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

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

n = int(input())
a = input().split()

b = []
if n % 2:
    flg = False
else:
    flg = True
for v in a:
    if flg:
        b.append(v)
        flg = False
    else:
        b.insert(0,v)
        flg = True

print(' '.join(b))

### FIXED CODE ###

n = int(input())
a = input().split()
reb_a = a[::-1]
if n % 2 == 0:
    res = reb_a[::2]+a[::2]
else:
    res = reb_a[::2]+a[1::2]

print(' '.join(res))
### BUGGY CODE ###

def get_item(L,i): return L[i] if len(L) > i else -2

def dw_heap(A,i):
    l = i*2 + 1
    r = (i+1)*2
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(A,r) > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        dw_heap(A, largest)


def up_heap(A,i):
    if i==0: return
    p = i//2 if i%2 == 1 else i//2 - 1
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def insert(A,k):
    A.append(k)
    up_heap(A,len(A)-1)


def extract(A):
    A[0],A[-1] = A[-1],A[0]
    max_item = A.pop()
    dw_heap(A,0)
    return max_item


if __name__=='__main__':
    hp = []
    while True:
        op = input().split() 
        if   op[0] == 'end': break
        if   op[0] == 'insert': insert(hp,int(op[1]))
        else: print(extract(hp))

### FIXED CODE ###

from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')
### BUGGY CODE ###

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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            a = [i, j, k]
            l = 0
            for s in S:
                if l < 3  and a[l] == int(s):
                    l += 1
            if l == 3:
                ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            a = [i, j, k]
            l = 0
            for s in S:
                if l < 3  and a[l] == int(s):
                    l += 1
            if l == 3:
                ans += 1

print(ans)
### BUGGY CODE ###

import bisect

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))

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

i = 0
for bc in BC:
    ti = bisect.bisect(A[i:], bc[1]) + i
    if (ti > i) and (bc[0] >= (ti - i)):
        A[i:ti] = [bc[1]] * (ti - i)
        i = ti
    elif (ti > i) and (bc[0] < (ti - i)):
        A[i:i + bc[0]] = [bc[1]] * bc[0]
        i = i + bc[0]

print(sum(A))


### FIXED CODE ###

import bisect

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))

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

ans, i = 0, 0
for bc in BC:
    ti = bisect.bisect(A, bc[1])
    if (ti > i) and (bc[0] >= (ti - i)):
        ans += bc[1] * (ti - i)
        i = ti
    elif (ti > i) and (bc[0] < (ti - i)):
        ans += bc[1] * bc[0]
        i = i + bc[0]

print(ans + sum(A[i:]))
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    # n+1なのはノード番号とリストのインデックスを一致させるため
    # root[x]<0ならそのノードが根かつその絶対値が木の要素数
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  
  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
    
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1
 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
  
n, k, l = map(int, input().split())
UFd= UnionFind(n)
UFt= UnionFind(n)

for i in range(k):
  p, q = map(int, input().split())
  UFd.Unite(p, q)

for j in range(l):
  p, q = map(int, input().split())
  UFt.Unite(p, q)
  
ids = []
d = {}
for i in range(n):
  if UFd.root[i+1] > 0:
    idd = UFd.root[i+1]
  else:
    idd = i+1
  if UFt.root[i+1] > 0:
    idt = UFt.root[i+1]
  else:
    idt = i+1
  iddt = idd*10**6+idt
  ids.append(iddt)
  if iddt in d:
    d[iddt] += 1
  else:
    d[iddt] = 1
ans = ''
for i in range(n):
  if i != 0:
    ans += ' '
  ans += str(d[ids[i]])
print(ans)    

### FIXED CODE ###

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

n, k, l = map(int, input().split())
rpar = [-1]* n
tpar = [-1]* n
rrank = [0]*n
trank = [0]*n

for i in range(k):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, rpar, rrank) 

for i_ in range(l):
  p, q = map(int, input().split())
  p, q =p-1, q-1
  Unite(p,q, tpar, trank)

d = {}
IDs = [0]*n
for j in range(n):
  ID = Find(j, rpar)+(Find(j, tpar)+1)*10**8
  IDs[j] = ID
  if ID in d:
    d[ID] += 1
  else:
    d[ID] = 1

ans = ''
for j_ in range(n):
  if j_ != 0:
    ans += ' '
  ans += str(d[IDs[j_]])
print(ans)
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []
if n % 2:
    for i in range(n):
        if i % 2 == 0:
            b.insert(0, a[i])
        else:
            b.append(a[i])
else:
    for i in range(n):
        if i % 2:
            b.insert(0, a[i])
        else:
            b.append(a[i])

print(' '.join(b))


### FIXED CODE ###

n = int(input())
a = input().split()
even = a[::2]
odd =a [1::2]

if n % 2:
    even = even[::-1]
    b = even + odd
else:
    odd = odd[::-1]
    b = odd + even

print(' '.join(b))
### BUGGY CODE ###

n = int(input())
a = []

for i in range(n):
  a.append(int(input()))

for j in range(n):
  tmp = a[j]
  a[j] = 0
  print(max(a))
  a[j] = tmp

### FIXED CODE ###

n = int(input())
a = []
a_sort = []

for i in range(n):
  a.append(int(input()))

m1 = max(a)
m2 = sorted(a)[-2]
  
for j in range(n):
  if a[j] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
zero_update = np.zeros(U,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
if c != 0:
  answer = arr[c,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)
### BUGGY CODE ###

from bisect import bisect_right
from bisect import bisect_left

n = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lg = L[i] + L[j] - 0.5
        st = L[j] - L[i] + 0.5
        m2 = bisect_left(L[j+1:],st)
        m1 = bisect_right(L[j+1:],lg)
        c += max(0,m1-m2)
print (c)

### FIXED CODE ###

import math
from bisect import bisect_right
from bisect import bisect_left

n = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lg = L[i] + L[j]
        st = L[j] - L[i]
        if lg > L[j+1] and st < L[n-1]:
            if lg > L[n-1]:
                m1 = n - (j+1)
            else:
                m1 = bisect_left(L[j+1:],lg)
            c += max(0,m1)
print (c)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    # edge[i]:頂点iからの[行先, 必要な銀貨, 時間]
    edge = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    # 銀貨との交換を自己ループとする
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    # [時間, 所持金, 頂点]
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            for i in range(ng, -1, -1):
                if dp[nv][i] > t+b:
                    dp[nv][i] = t+b
                else:
                    break
            heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    # edge[i]:頂点iからの[行先, 必要な銀貨, 時間]
    edge = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    # 銀貨との交換を自己ループとする
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    # [時間, 所持金, 頂点]
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            if dp[nv][ng] > t+b:
                dp[nv][ng] = t+b
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**9 + 7

dp = [inf] * n
dp[0] = 0

for i in range(n):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])


### FIXED CODE ###

inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
# for i in range(n):
#     for j in range(1, min(k+1, n-i)):
#         dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])
### BUGGY CODE ###

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

N = int(input())

ans = 0

for a in range(1, N+1):
  for b in range(1, N+1):
    d = gcd(a,b)
    for c in range(1, N+1):
      ans += gcd(d,c)
      
print(ans)

### FIXED CODE ###

from math import gcd

N = int(input())

ans = 0

for a in range(1, N+1):
  for b in range(1, N+1):
    d = gcd(a,b)
    for c in range(1, N+1):
      ans += gcd(d,c)
      
print(ans)
### BUGGY CODE ###

n, q = map(int,input().split())
s = input()
lr_list = []
#for i in range(q):
#    lr_list.append(list(map(int,input().split())))
ans_list = []
for i in range(q):
#    l,r = lr_list[i]
    l,r = map(int,input().split())
    ans_list.append(s[l-1:r].replace('AC','1').count('1'))
for i in range(q):
    print(ans_list[i])

### FIXED CODE ###

n, q = map(int,input().split())
s = input()
ruiseki = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        ac = 1
    else:
        ac = 0
    ruiseki[i+1] = ruiseki[i] + ac
ans_list = []
for i in range(q):
    l,r = map(int,input().split())
    ans_list.append(ruiseki[r-1]-ruiseki[l-1])
for i in range(q):
    print(ans_list[i])
### BUGGY CODE ###

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**12
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)


### FIXED CODE ###

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

n, k = map(int, input().split())
li = list(map(int, input().split()))
li_a = sorted(li)
if k == 0:
  print(sum(li_a))
elif k >= n:
  print(0)
else:
  for i in range(k):
    a = li_a[-1]
    li_a.remove(a)
  print(sum(li_a))

### FIXED CODE ###

n, k = map(int, input().split())
li = list(map(int, input().split()))
li_a = sorted(li)
if k == 0:
  print(sum(li_a))
elif k >= n:
  print(0)
else:
  for i in range(k):
    li_a.pop()
  print(sum(li_a))
### BUGGY CODE ###

N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
L.sort(key=lambda x: x[0])
funes1 = []
for a,b in L:
    if a != 1:
        break
    funes1.append(b)
funes1.sort()
for f in funes1:
    for a,b in L:
        if a > f:
            break
        if f == a:
            if b == N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')




### FIXED CODE ###

N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
L.sort(key=lambda x: x[0])
funes1 = [False]*N
for a,b in L:
    if a == 1:
        funes1[b] = True
    else:
        if funes1[a]:
            if b == N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def sol(n, q, s, ll, lr):
    aas = []
    for i in range(1,n):
        if s[i-1]=="A" and s[i]=="C":
            aas.append(i)
    rsw = [0]
    a = 0

    for i in range(1,n+1):
        if i in aas:
            a += 1
        rsw.append(a)
    for i in range(q):
        ans = rsw[lr[i]-1]-rsw[ll[i]-1]
        print(ans)

def main():
    import sys
    input = sys.stdin.readline 
    l = list(map(int, input().split()))
    n = l[0]
    q = l[1]
    s = input()
    ll = []
    lr = []
    for i in range(q):
        l, r = list(map(int, input().split()))
        ll.append(l)
        lr.append(r)
    sol(n,q,s,ll,lr)

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n, q = map(int, input().split())
s=input().rstrip("\n")

cnt=[0]
c=0
for i in range(n-1):
    if s[i:i+2]=="AC":
        c+=1
    cnt.append(c)
#print(cnt)
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[r-1]-cnt[l-1])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

while (num < n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
    if (len(visit) == 0):
        day = -1
        break
print(day)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)