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

# coding: utf-8
from collections import deque
N = int(input())
S = input()
Sd = deque(S)
ans = 0
R, G, B = [], [], []
for i in range(N):
    p = Sd.popleft()
    if p == "R":
        R.append(i)
    elif p == "G":
        G.append(i)
    else:
        B.append(i)
for r in R:
    for g in G:
        for b in B:
            if g - r != b - g and r < g < b:
                # L.append((r,g,b))
                ans += 1
    for b in B:
        for g in G:
            if b - r != g - b and r < b < g:
                # L.append((r,g,b))
                ans += 1
                
for g in G:
    for b in B:
        for r in R:
            if b - g != r - b and g < b < r:
                # L.append((r,g,b))
                ans += 1
    for r in R:
        for b in B:
            if r - g != b - r and g < r < b:
                # L.append((r,g,b))
                ans += 1

for b in B:
    for g in G:
        for r in R:
            if g - b != r - g and b < g < r:
                # L.append((r,g,b))
                ans += 1
    for r in R:
        for g in G:
            if r - b != g - r and b < r < g:
                # L.append((r,g,b))
                ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
from collections import deque
N = int(input())
S = input()
Sd = deque(S)
ans = 0
R, G, B = 0, 0, 0
for i in range(N):
    p = Sd.popleft()
    if p == "R":
        R += 1
    elif p == "G":
        G += 1
    else:
        B += 1
ans = R * G * B
for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k >= N:
            continue
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab = sorted(ab, key=lambda x:x[1], reverse=True)

dellist = lambda items,indices: [item for idx,item in enumerate(items) if idx not in indices]

count = 0
while len(ab) != 0:
  p = ab.pop()
  count += 1
  del_idx = []
  for i in range(len(ab)):
    if ab[i][0] < p[1]:
      del_idx.append(i)
  ab = dellist(ab, del_idx) # ['japanese','!!']
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab = sorted(ab, key=lambda x:x[1])
count = 0

del_num = 0
for i in range(M):
  if ab[i][0] >= del_num:
    count += 1
    del_num = ab[i][1]
print(count)
### BUGGY CODE ###

#OK牧場
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
#こっちは変えられない
f=sorted(list(map(int,input().split())),reverse=True)
l,r=0,10**12
def cal(x):
    global n,f,a,k
    ret=0
    for i in range(n):
        ret+=max(0,a[i]-(x//f[i]))
    #print(ret,x)
    return ret
while l+1<r:
    x=l+(r-l)//2
    if cal(x)<=k:
        r=x
    else:
        l=x
if cal(l)<=k:
    print(l)
else:
    print(r)

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
#こっちは変えられない
f=sorted(list(map(int,input().split())),reverse=True)
l,r=0,10**12
def cal(x):
    global n,f,a,k
    ret=0
    for i in range(n):
        ret+=max(0,a[i]-(x//f[i]))
    #print(ret,x)
    return ret
while l+1<r:
    x=l+(r-l)//2
    if cal(x)<=k:
        r=x
    else:
        l=x
if cal(l)<=k:
    print(l)
else:
    print(r)
### BUGGY CODE ###

N = int(input())
import numpy as np
li = np.array([0]*N)


for i in range(N):
    li[i:N:i+1]+=1

print(sum(i*a for i,a in enumerate(li,1)))

### FIXED CODE ###

N = int(input())

counter = 0
for n in range(1,N+1):
    a = N//n
    counter += a*(a+1)*n//2


print(counter)
### BUGGY CODE ###

# import sys
# input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d
# dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        # 使わないとき
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        # 使うとき
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
C = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
    c = list(map(int, input().split()))
    C[i] = c
D = [0] * m
for i in range(m):
    d = 0
    for j in C[i]:
        d |= 1 << (j - 1)
    D[i] = d
# dp[i][s], i番目までの鍵を使ってSを作る最小コスト
infi = 10 ** 20
dp = [[infi for i in range(2 ** n + 1)] for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for s in range(2 ** n):
        ni = i + 1
        ns = s
        # 使わないとき
        dp[ni][ns] = min(dp[i][s], dp[ni][ns])
        # 使うとき
        ns = s | D[i]
        dp[ni][ns] = min(dp[ni][ns], dp[i][s] + A[i])
ans = dp[m][2 ** n - 1]
print(ans if ans < infi else -1)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]

ans=float('inf')
for i in range(1,n):
    ans=min(ans, abs(sum(a[:i])-sum(a[i:])))

print(ans)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
su=sum(a)
ans=float('inf')
check=a[0]
for i in range(1,n):    
    check2=su-check
    ans=min(ans, abs(check-check2))
    check+=a[i]

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

import numpy as np

n, w = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+8) for _ in range(n+10)]
weight = [0] * (n)
value = [0] * (n)

for i in range(n):
    weight[i] = li[i][0]
    value[i] = li[i][1]

for i in range(n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j - weight[i]] + value[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+8) for _ in range(n+10)]
weight = [0] * (n)
value = [0] * (n)

for i in range(n):
    weight[i] = li[i][0]
    value[i] = li[i][1]

for i in range(n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j - weight[i]] + value[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[n][w])
### BUGGY CODE ###

import queue

H,W=map(int,input().split())
G=[list(str(input())) for _ in range(H)]
P=10**9+7


def sur(v):#v is tuple
    global H
    global W
    global G

    vx=v[0]
    vy=v[1]
    preE=[(vx+1,vy),(vx,vy+1)]
    E=[]
    for e in preE:
        if 0<=e[0]<H and 0<=e[1]<W:
            if G[e[0]][e[1]]=='.':
                E.append(e)
    return E

#DP[i][j]=(i+1,j+1)までの行き方の総数
DP=[[0]*W for row in range(H)]
DP[0][0]=1


#BFS
q=queue.Queue()
q.put((0,0))
L=set()
while not q.empty():
    now=q.get()
    for next in sur(now):
        DP[next[0]][next[1]]+=DP[now[0]][now[1]]
        DP[next[0]][next[1]]=DP[next[0]][next[1]]%P
        if next in L:
            continue
        q.put(next)
        L.add(next)
        #if next==(H-1,W-1):
            #print(now,next,L)

#for i in range(H):
    #string=''
    #for j in range(W):
        #if G[i][j]=='#':
            #string+=G[i][j]+' '
        #else:
            #string+=str(DP[i][j])+' '
    #print(string)
        
print(DP[H-1][W-1])



### FIXED CODE ###

H,W=map(int,input().split())
G=[list(str(input())) for _ in range(H)]
P=10**9+7

DP=[[0]*(W+1) for _ in range(H+1)]
DP[1][1]=1

for i in range(1,H+1):
    for j in range(1,W+1):
        if G[i-1][j-1]=='#':
            DP[i][j]=0
        else:
            DP[i][j]+=DP[i-1][j]+DP[i][j-1]
            DP[i][j]=DP[i][j]%P


print(DP[H][W])
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
MAX_N = 4 * 10 ** 5
# MAX_N = 20


def init(n_):
    #簡単にするために2のべき乗に揃える
    n = 1
    while n < n_:
        n *= 2
    return n

#初期化
N = int(input())
n = init(N)
data = [0] * (2 * MAX_N - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        k = (k - 1) // 2
        data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

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

ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, tmp + a)
    ans = max(ans, tmp + a)
    # print (data)

print (ans)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

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

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

import bisect

N,M,Q = map(int,input().split())
LR = []
for i in range(M):
    L,R = map(int,input().split())
    LR.append((L,R))
LR = sorted(LR)
L = [t[0] for t in LR]
R = [t[1] for t in LR]
#print(LR)
pq = []
for i in range(Q):
    pq.append(list(map(int,input().split())))
for i in range(Q):
    p,q = pq[i]
    left = bisect.bisect_left(L,p)
    #print(left,M)
    #print(R[left:M])
    ans = len(list(filter(lambda t:t <= q, R[left:M])))
    print(ans)


### FIXED CODE ###

N,M,Q = map(int,input().split())
LR = [[0 for x in range(N+1)] for y in range(N+1)]
for i in range(M):
    L,R = map(int,input().split())
    LR[L][R] += 1

LRsum = [[0 for x in range(N+1)] for y in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        LRsum[i][j] = LRsum[i][j-1] + LR[i][j]

pq = []
for i in range(Q):
    pq.append(list(map(int,input().split())))
for i in range(Q):
    p,q = pq[i]
    ans = 0
    for i in range(p,q+1):
        ans += LRsum[i][q] - LRsum[i][p-1]
    print(ans)
### BUGGY CODE ###

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

max=1
for i in range(K):
    max*=A[i]
for i in range(K,N):
    if max<(max//A[i-K])*A[i]:
        print("Yes")
        max=(max//A[i-K])*A[i]
    else:
        print("No")

### FIXED CODE ###

#C
import math
N,K=map(int,input().split())
A=list(map(int,input().split()))

for i in range(N):
    A[i]=math.log10(A[i])
max=0
for i in range(K):
    max+=A[i]
for i in range(K,N):
    if max<max-A[i-K]+A[i]:
        print("Yes")
        max=max-A[i-K]+A[i]
    else:
        print("No")
### BUGGY CODE ###

def main():
    n = int(input())
    count = 0
    lists =[]
    count_dict = {}

    for i in range(n):
        input_data = ''.join(sorted(input()))
        if input_data in lists:
            if input_data not in count_dict.keys():
                count_dict[input_data] = 1
            count = count + count_dict[input_data]
            count_dict[input_data] += 1
        else:
            lists.append(input_data)

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)
### BUGGY CODE ###

def len_LCS(X,Y):
    lcs = [[0 for _ in range(len(X)+1)] for _ in range(len(Y)+1)]
    for j in range(len(Y)):
        for i in range(len(X)):
            if Y[j] == X[i]:
                lcs[j+1][i+1] = lcs[j][i] + 1
            else:
                lcs[j+1][i+1] = max(lcs[j+1][i], lcs[j][i+1])
    return lcs[-1][-1]

if __name__=='__main__':
    q = int(input())
    for _ in range(q):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

### FIXED CODE ###

def len_LCS(X,Y):
    lcs_row = [0 for _ in range(len(X)+1)]
    for yc in Y:
        lcs_row_p = lcs_row[:]
        # lcs_row_p: [i] [i+1]
        # lcs_row  : [i] [i+1]
        for (i,xc) in enumerate(X):
            if xc == yc:
                lcs_row[i+1] = lcs_row_p[i] + 1
            elif lcs_row[i] > lcs_row_p[i+1]:
                lcs_row[i+1] = lcs_row[i]
    return lcs_row[-1]
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[[xs,ys,0],[xt,yt,0]]
  xyr+=[list(map(int,input().split())) for _ in range(n)]
  memo={}
  def dist(xyr,i,j):
    if i<j:
      i,j=j,i
    if (i,j) in memo:return memo[(i,j)]
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    memo[(i,j)]=d
    return d
  from heapq import heappop,heappush
  todo=[[0,0]]
  ka=set(())
  seen=[-1]*(n+2)
  seen[0]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==1:
      print(d)
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]==-1 or seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

from bisect import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
count = 0
for i in range(N):
    minb = bisect(B, A[i])
    if minb == N:
        break
    for j in range(minb, N):
        if B[j] == A[i]:
            continue
        minc = bisect(C, B[j])
        if minc == N:
            break
        count += N - minc
print(count)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
print(sum(bisect.bisect_left(A, i)*(N-bisect.bisect_right(C, i)) for i in B))
### BUGGY CODE ###

N = int(input())
E = [i+1 for i in range(N)]
A = list(map(int,input().split()))
A.insert(0,0)

for i in range(N):
    print(A.count(i+1))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Ansbox = [0]*(N+1)

def count(N,A,Ansbox):

    for i in range(N- 1):
        Ansbox[A[i] - 1] += 1
        
    for i in range(N):
        print(Ansbox[i])
        
count(N,A,Ansbox)
### BUGGY CODE ###

n = int(input())
s = [int(input()) for i in range(n)]

point = [0]
for i in range(2**n):
    cnt = 0
    for j in range(n):
        if ((i >> j)&1):
            cnt += s[j]
    if cnt%10 != 0:
        point.append(cnt)
print(max(point))

### FIXED CODE ###

N = int(input())
s = sorted([int(input()) for _ in range(N)])

l10 = []
l = []

for i in s:
    if i%10:
        l.append(i)
    else:
        l10.append(i)

ss = l + l10
# print(s)
# print(ss)
if sum(ss)%10 == 0:
    while sum(ss)%10 == 0:
        # print(s)
        if ss:
            ss.pop(0)
        else:
            break
    ans = sum(ss)
else:
    ans = sum(ss)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N=int(input())
ab=[[] for _ in range(N)]
for _ in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)


def dfs(p,pa):
  global path
  if p==N:
    path=pa
  else:
    for i in ab[p-1]:
      if i not in pa:
        dfs(i,pa+[i])

dfs(1,[1])

def dfs2(p):
  a=0
  seen.append(p)
  for i in ab[p-1]:
    if i in path:
      pass
    elif i in seen:
      pass
    else:
      a+=dfs2(i)
  return 1+a

ff=0
sf=0
L=len(path)
for i in range(L):
  seen=[]
  if i<=(L-1)//2:
    ff+=dfs2(path[i])
  else:
    sf+=dfs2(path[i])
    
if ff>sf:
  print("Fennec")
else:
  print("Snuke")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N=int(input())
ab=[[] for _ in range(N)]
for _ in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)
"""
N=10**5
ab=[[]]*N
ab[0]=[2]
ab[N-1]=[N-1]
for i in range(1,N-1):
  ab[i]=[i,i+2]
"""
par=[0]*N
  
def dfs(pre,p):
  global path
  par[p-1]=pre
  if p==N:
    pass
  else:
    for i in ab[p-1]:
      if i!=pre:
        dfs(p,i)

dfs(-1,1)
path=[N]
p=N
while p!=1:
  p=par[p-1]
  path.append(p)
path.reverse()

spath=set(path)

def dfs2(pre,p):
  a=0
  for i in ab[p-1]:
    if i in spath:
      pass
    elif i==pre:
      pass
    else:
      a+=dfs2(p,i)
  return 1+a

ff=0
sf=0
L=len(path)
for i in range(L):
  if i<=(L-1)//2:
    ff+=dfs2(-1,path[i])
  else:
    sf+=dfs2(-1,path[i])
    
if ff>sf:
  print("Fennec")
else:
  print("Snuke")
### BUGGY CODE ###

n, m = map(int, input().split())
one_next = []
n_next = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        one_next.append(b)
    elif b == n:
        n_next.append(a)

for num in one_next:
    if num in n_next:
        print("POSSIBLE")
        break
else:
     print("IMPOSSIBLE")       

### FIXED CODE ###

n, m = map(int, input().split())
ans = [0 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ans[b - 1] += 1
    elif b == n:
        ans[a - 1] += 1

if 2 in ans:
    print("POSSIBLE")
else:
     print("IMPOSSIBLE")
### BUGGY CODE ###

import bisect
N=int(input())
A=sorted(list(map(int, input().split())))
B=sorted(list(map(int, input().split())))
C=sorted(list(map(int, input().split())))
D=[0]*N
E=[0]*N
for i in range(N):
    D[i]=N-bisect.bisect_right(C,B[i])
for i in range(N):
    E[i]=sum(D[bisect.bisect_right(B,A[i]):])
print(sum(E))

### FIXED CODE ###

import bisect
N=int(input())
A=sorted(list(map(int, input().split())))
B=sorted(list(map(int, input().split())))
C=sorted(list(map(int, input().split())))
ans=0
for i in range(N):
    ans+=(bisect.bisect_left(A,B[i]))*(N-bisect.bisect_right(C,B[i]))
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
cnt = 0
for i in range(q):
    l, r = map(int, input().split())
    for j in range(l - 1, r - 1):
        if s[j] == "A" and s[j + 1] == "C":
            cnt += 1
    print(cnt)
    cnt = 0


### FIXED CODE ###

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

N=int(input())
A=list(map(int,input().split()))
A.sort()
C=[]
while len(A)>0:
    c=len(A)
    a=A[0]
    if len(A)>1 and A[1]==a:
        pass
    else:
        C.append(a)
    A=[A[j] for j in range(c) if A[j]%a!=0]
print(len(C))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
TF={a:True for a in A}
for i in range(N):
    if TF[A[i]]==True:
        if i > 0 and A[i - 1] == A[i]:
            TF[A[i]] = False
        m=A[N-1]//A[i]
        for j in range(2,m+1):
            s=A[i]*j
            if s in TF:
                TF[s]=False
print(len([1 for a in A if TF[a]==True]))
### BUGGY CODE ###

#16D8104025G 佐藤智裕 mist75__ Python3

class DLL:
    class Node:
        def __init__(self, x, y, z):
            self.v = x
            self.prv = y
            self.nxt = z

    def __init__(self):
        init = DLL.Node(None, None, None)
        init.prv = init
        init.nxt = init
        self.size = 0
        self.init = init

    def insert(self, x):
        i = self.init
        j = i.nxt
        k = DLL.Node(x, i, j)
        i.nxt = k
        j.prv = k
        self.size += 1

    def deleteFirst(self):
        if self.size != 0:
            i = self.init
            k = i.nxt
            j = k.nxt
            i.nxt = j
            j.prv = i
            self.size -= 1

    def deleteLast(self):
        if self.size != 0:
            i = self.init
            k = i.prv
            j = k.prv
            i.prv = j
            j.nxt = i
            self.size -= 1

    def delete(self, x):
        if self.size != 0:
            i = self.init
            k = i.nxt
            while 1:
                if k.v == x:
                    i = k.prv
                    j = k.nxt
                    i.nxt = j
                    j.prv = i
                    self.size -= 1
                    break
                else:
                    if k.nxt == i:
                        break
                    else:
                        k = k.nxt

    def prt(self):
        f = self.init
        s = f.nxt
        l = f.prv
        while 1:
            if s != l:
                print(s.v, end=' ')
                s = s.nxt
            else:
                print(l.v)
                break

n = int(input())
L = DLL()

for i in range(n):
    com = input()
    if com == "deleteFirst":
        L.deleteFirst()
    elif com == "deleteLast":
        L.deleteLast()
    else:
        C = com.split()
        if C[0] == "insert":
            L.insert(int(C[1]))
        elif C[0] == "delete":
            L.delete(int(C[1]))
    #L.prt()
    
L.prt()



### FIXED CODE ###

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    else:
        if com[6] == 'F':
            L.popleft()
        elif com[6] == 'L':
            L.pop()
        else:
            C = com.split()
            x = int(C[1])
            try:
                L.remove(x)
            except:
                pass

print(*L)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []

for i in range(n):
    tmp = a.pop(0)
    b.append(tmp)
    b = b[::-1]
    

print(*b)

### FIXED CODE ###

n = int(input())
a = list(input().split())
print(" ".join(a[::-2] + a[n%2::2]))