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

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
x = []
values = []
combs = []

for i in set(s):
  if s.count(i) > 1:
    values.append(s.count(i))
for i in values:
  combs.append(i*(i-1)//2)
print(sum(combs))

### FIXED CODE ###

import collections
n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
#values = []
combs = 0
c = collections.Counter(s)
# このfor文を削減するためにcollections.Counter()を使用
# for i in set(s):
#   if s.count(i) > 1:
#     values.append(s.count(i))
for i in c.values():
  combs+=i*(i-1)//2
print(combs)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


def another(c):
    if c == "#": return "."
    if c == ".": return "#"


def search(x, y):
    checked[y][x] = True
    now = mp[y][x]
    if mp[y][x] == "#":
        b_cnt = 1
        w_cnt = 0
    else:
        b_cnt = 0
        w_cnt = 1
    for dx, dy in vec:
        if not checked[y + dy][x + dx] and mp[y + dy][x + dx] == another(now):
            w_add, b_add = search(x + dx, y + dy)
            w_cnt += w_add
            b_cnt += b_add
    return w_cnt, b_cnt

ans = 0
for y in range(1, h + 1):
    for x in range(1, w + 1):
        if not checked[y][x]:
            w_cnt, b_cnt = search(x, y)
            ans += w_cnt * b_cnt

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def main():
    h, w = map(int, input().split())
    mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
    checked = [[False] * (w + 2) for _ in range(h + 2)]
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


    def search(stack):
        x, y = stack.pop()
        if mp[y][x] == "#":
            b_cnt = 1
            w_cnt = 0
            another = "."
        else:
            b_cnt = 0
            w_cnt = 1
            another = "#"
        for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if not checked[ny][nx] and mp[ny][nx] == another:
                checked[ny][nx] = True
                stack.append((nx, ny))
        return w_cnt, b_cnt

    ans = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if not checked[y][x]:
                checked[y][x] = True
                stack = []
                stack.append((x, y))
                w_cnt = b_cnt = 0
                while stack:
                    w_add, b_add = search(stack)
                    w_cnt += w_add
                    b_cnt += b_add
                ans += w_cnt * b_cnt

    print(ans)

main()
### BUGGY CODE ###

a, b, k = map(int, input().split())
length = b+1 -a
index = []

for i in range(length):
    if i <= k-1 or length-1-i<=k-1:
        index.append(i)

for i in index:
    print(a+i)

### FIXED CODE ###

a, b, k = map(int, input().split())
length = b+1 -a
num = []

for i in range(a, min(b, a+k-1)+1):
    print(i)
    num.append(i)
for i in range(max(a, b - (k-1)), b+1):
    if i not in num:
        num.append(i)
        print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from heapq import heappush, heappop

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

# A日後、報酬B
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

sum = 0
used = [False] * n
for i in range(0, m):
    # A <= iで未使用のものをheapqに入れる
    hq = []
    for j in range(n):
        # print(a[j], i+1,a[j]<=i+1, not used[j])

        if a[j] <= i + 1 and not used[j]:
            heappush(hq, (-b[j], j, a[j]))

    val = None
    if len(hq) > 0:
        val = heappop(hq)
    if val is not None:
        sum += -val[0]
        used[val[1]] = True

print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

from heapq import heappush, heappop

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

# A日後、報酬B
workList = {}
for i in range(n):
    a, b = map(int, input().split())
    if a not in workList:
        workList[a] = [-b]
    else:
        workList[a].append(-b)
# print(workList)

hq = []
sum = 0
for i in range(1, m + 1):
    if i in workList:
        for w in workList[i]:
            heappush(hq, w)

    val = None
    if len(hq) > 0:
        val = heappop(hq)
    if val is not None:
        sum += -val

print(sum)
### BUGGY CODE ###

from functools import lru_cache

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

@lru_cache(maxsize=300000)
def dp(i, a):
    if i == 0:
        return action[0][a]
    else:
        return max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))


### FIXED CODE ###

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))
### BUGGY CODE ###

#d
h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
s = [input() for _ in range(h)]
inf = 99999999
dist = [[inf]* w for i in range(h)]
queue = []
queue.append([ch-1,cw-1])
dist[ch-1][cw-1] = 0

dx=[1,0,-1,0]
dy=[0,1,0,-1]

wx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy=[-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
import sys
warp = 0
wall = []
while True:
    while queue!=[]:
        y,x = map(int, queue.pop())

        if x == dw-1 and y ==dh-1:
            print(dist[y][x])
            sys.exit()

        for i in range(len(dx)):#まず壁探知
            next_x = x +dx[i]
            next_y = y +dy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]
                    else:
                        wall.append([y,x]) 
    while wall != []:
        y,x = map(int, wall.pop())
        for i in range(len(wx)):
            next_x = x +wx[i]
            next_y = y +wy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]+1


### FIXED CODE ###

#d
h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
s = [input() for _ in range(h)]
inf = 99999999
dist = [[inf]* w for i in range(h)]
queue = []
queue.append([ch-1,cw-1])
dist[ch-1][cw-1] = 0

dx=[1,0,-1,0]
dy=[0,1,0,-1]

wx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy=[-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
import sys
warp = 0
wall = []
while True:
    while queue!=[]:
        y,x = map(int, queue.pop())

        if x == dw-1 and y ==dh-1:
            print(dist[y][x])
            sys.exit()

        for i in range(len(dx)):#まず壁探知
            next_x = x +dx[i]
            next_y = y +dy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]
                    else:
                        wall.append([y,x]) 
    wall = list(map(list, set(map(tuple, wall))))
    while wall != []:
        y,x = map(int, wall.pop())
        for i in range(len(wx)):
            next_x = x +wx[i]
            next_y = y +wy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]+1
    queue = list(map(list, set(map(tuple, queue))))
    
    if queue == []:
        print("-1")
        sys.exit()
### BUGGY CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

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

min_diff = 1
max_diff = N - 1

count = 0
for diff in range(min_diff, max_diff + 1):
    pairs = []
    i = 1
    while True:
        j = i + diff
        if j <= N:
            pairs.append([i, j])
        else:
            break
        i += 1
    # pprint(pairs)
    for i, j in pairs:
        if abs(i - j) == A[i-1] + A[j-1]:
            count += 1

print(count)


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import math
import itertools
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

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

min_diff = 1
max_diff = N - 1

dl = defaultdict(list)
dr = defaultdict(list)
for i in range(1, N + 1):
    key = i + A[i-1]
    dl[key].append(i)
    key = i - A[i-1]
    if key > 0:
        dr[key].append(i)
# pprint(dict(dl))
# pprint(dict(dr))

count = 0
for diff in range(min_diff, max_diff + 1):
    count += len(dl[diff]) * len(dr[diff])
print(count)
### BUGGY CODE ###

from collections import defaultdict
Poll_Dict = defaultdict(int)

N = int(input())

for i in range(N):
    Poll_Dict[str(input())] += 1
Max_List = sorted([k[0] for k in Poll_Dict.items() if k[1] == max(Poll_Dict.values())])

for i in Max_List:
    print(i)

### FIXED CODE ###

from collections import defaultdict
Poll_Dict = defaultdict(int)

N = int(input())

for _ in range(N):
    Poll_Dict[str(input())] += 1

Max_Number = max(Poll_Dict.values())    
Max_List = sorted([k[0] for k in Poll_Dict.items() if k[1] == Max_Number])

for i in Max_List:
    print(i)
### BUGGY CODE ###



s = input()
queNum = int(input())

for _ in range(queNum):
    query = input()

    if query == '1':
        s = s[::-1]
    else:
        num, fi, ci = query.split()
        if fi == '1':
            s = ci + s
        else:
            s = s + ci
    
print(s)

### FIXED CODE ###



s = input()
queNum = int(input())


reverse_cnt = 0
begin_lst = []
end_lst = []
for _ in range(queNum):
    query = input()

    if query == '1':
        reverse_cnt += 1
        begin_lst, end_lst = end_lst, begin_lst
    else:
        num, fi, ci = query.split()
        if fi == '1':
            begin_lst.append(ci)
        else:
            end_lst.append(ci)
    
if reverse_cnt % 2 == 0:
    pass
else:
    s = s[::-1]

print(''.join(reversed(begin_lst)) + s + ''.join(end_lst))
### BUGGY CODE ###

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0
for i, a in enumerate(l_ls):
    for j, b in enumerate(l_ls):
        if i == j:
            continue
        for k, c in enumerate(l_ls):
            if i == k or j == k:
                continue

            if a < b+c and b < c+a and c < a+b:
                ans += 1
print(ans//6)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        a, b = l_ls[i], l_ls[j]
        right = bisect_left(l_ls, a+b)
        ans += right-(j+1)

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

import heapq
N,M = map(int,input().split())
list_A = list(map(int,input().split()))	

list_A = list(map(lambda x: x*(-1), list_A))

#print(list_A)

for i in range(M):
  heapq.heapify(list_A)
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  target = -1*((-1 *target) // 2)
  
  heapq.heappush(list_A, target)  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(sum(list_A)*-1)




### FIXED CODE ###

import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)
heapq.heapify(list_A)
for i in range(M):
  
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  # 要素の挿入
  #print("No.",i,"change finished",list_A)

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

MOD = 1000000007

X,Y = map(int,input().split())
x,y = (2*X-Y)//3,(2*Y-X)//3#行動１、行動２を起こす回数
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or x < 0 or y < 0 or(x==0 and y==0):
    print(0)
    exit()
ans =1
for i in range(x+y,0,-1):
    ans = ((ans%MOD)*i)%MOD
for i in range(x,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD
for i in range(y,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD

print(ans)


### FIXED CODE ###

MOD = 1000000007

X,Y = map(int,input().split())
x,y = (2*X-Y)//3,(2*Y-X)//3#行動１、行動２を起こす回数
if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or x < 0 or y < 0 or(x==0 and y==0):
    print(0)
    exit()
ans =1
for i in range(x+y,0,-1):
    ans = ((ans%MOD)*i)%MOD
for i in range(x,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD
for i in range(y,0,-1):
    ans = ((ans%MOD)*pow(i,MOD-2,MOD))%MOD

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

def lowerBound(nums, target):
    lp = 0
    rp = len(nums) - 1
    mp = lp + rp >> 1
    while lp <= rp:
        mp = lp + rp >> 1
        if nums[mp] == target:
            return mp
        if nums[mp] < target:
            lp = mp + 1
        else:
            rp = mp - 1
    return mp if target < nums[mp] else -1

if __name__ == '__main__':
    N = int(input())
    L = [int(l) for l in input().split()]
    L.sort()
    ret = 0
    for idx in range(len(L) - 1, 1, -1):
        for jdx in range(idx - 1, 0, -1):
            c = L[idx] - L[jdx] + 1
            ldx = lowerBound(L[:jdx], c)
            if ldx == -1: continue
            ret += len(L[ldx: jdx])
    print(ret)

### FIXED CODE ###

from bisect import *
if __name__ == '__main__':
    N = int(input())
    L = sorted(map(int, input().split()))
    print(sum(jdx - bisect(L, a - L[jdx], 0, jdx) for idx, a in enumerate(L) for jdx in range(idx)))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
L = []
for a in A:
  L.append(a)
  L.reverse()
s = str(L[0])
for i in range(1, len(L)):
  s = s + " " + str(L[i])
print(s)

### FIXED CODE ###

n = int(input())
A = list(input().split())
B = ""
m = n//2
if n%2 == 0:
  for i in range(m):
    B += A[n-1-2*i]
    B += " "
  for i in range(m):
    B += A[i*2]
    B += " "
else:
  for i in range(m+1):
    B += A[n-1-2*i]
    B += " "
  for i in range(m):
    B += A[i*2+1]
    B += " "
print(B[:-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
ans = 1
if N == 1:
    print(M)
    exit()
while ans > 0:
    ans = M // N
    if M % ans == 0 and M / ans >= N:
        break
    N += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
ans = 1
if N == 1:
    print(M)
    exit()

for n in range(2, int(M ** 0.5) +1):
    if M % n == 0:
        if n < N and M // n < N:
            continue
        elif n >= N and M // n < N:
            ans = max(ans, M // n)
        elif n < N and M // n >= N:
            ans = max(ans, n)
        else:
            ans = max(ans, n, M // n)

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

import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    Ls = []
    Rs = []
    for i in range(M):
        L,R=mi()
        Ls.append((L,i))
        Rs.append((R,i))

    Ls.sort()
    Rs.sort()

    L_indexs = [set()] * (M+1)
    R_indexs = [set()] * (M+1)

    _Ls = []
    _Rs = []
    for i in range(M):
        L,L_i = Ls[i]
        R,R_i = Rs[i]

        L_indexs[i+1] = L_indexs[i] | set([L_i])
        R_indexs[i+1] = R_indexs[i] | set([R_i])

        _Ls.append(L)
        _Rs.append(R)

        
        

    # print(L_indexs,R_indexs)
    for i in range(Q):
        p,q=mi()
        L_i = bisect.bisect_left(_Ls,p)

        # print(L_i)
        
        R_i = bisect.bisect_right(_Rs,q)
        if R_i == M:
            R_i -= 1
        elif Rs[R_i][0] != q:
            R_i -= 1

        ans = 0
        # print(L_i,R_i,L_indexs[-1] - L_indexs[L_i],R_indexs[R_i+1])
        for j in R_indexs[R_i+1]:
            if j in L_indexs[-1] - L_indexs[L_i]:
                ans += 1
        
        print(ans)



        




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    
    count = [[0] * (N+1) for _ in range(N+1)]
    for i in range(M):
        L,R=mi()
        count[L][R] += 1
    
    # print(count)
    dp = [[0] * (N+1) for _ in range(N+1)]

    for w in range(1,N+1):
        for h in range(1,N+1):
            l,r=N+1-w,h
            dp[w][h] += dp[w][h-1] + dp[w-1][h] - dp[w-1][h-1] + count[l][r]


    # print(dp)
    for i in range(Q):
        p,q=mi()
        w,h=N+1-p,q
        # print(w,h)
        print(dp[w][h])

            






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

import cProfile
n,m = map(int,input().split())
a = list(map(int, input().split()))
a.sort()
s = []
for i in range(m):
    b,c = map(int,input().split())
    s += [c]*b
    
s.sort()
s.reverse()
d = len(s)
#print(a[n-1])
for i in range(n):
    if s[0] > a[i]:
        a[i] = s[0]
        s.remove(s[0])
    else:
        break
    if i == d-1:
        break


print(sum(a))
#cProfile.run()



### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int, input().split()))
a.sort()
e =0
bc = []
for i in range(m):
    d = list(map(int,input().split()))
    bc.append([d[1],d[0]])
    e += d[0] 
#print(a)  
 
 
bc.sort()
bc.reverse()
#print(bc)
 
#print(e)
#print(a[n-1])
j = 0
for i in range(n):
    if j == bc[0][1] :
        bc.remove(bc[0])
        j = 0
    if bc[0][0] > a[i]:
        a[i] = bc[0][0]
        j += 1
    else:
        break
    if i == e-1:
        break
 
 
#print(a)
print(sum(a))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

edge = [[] for i in range(n)]

for i in range(m):
    l, r, d = map(int, input().split())
    l-=1;r-=1
    edge[l].append((r, d))
    edge[r].append((l, -d))

flag = True
for i in range(n):
    if not flag: break
    dist = [10**10]*n
    dist[i] = 0
    dq = deque([i])
    while dq:
        now = dq.popleft()
        for e in edge[now]:
            nnode, d = e
            if dist[nnode] == inf:
                dist[nnode] = dist[now] + d
                dq.append(nnode)
            else:
                if dist[nnode] != dist[now] + d:
                    flag = False
                    break
if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

edge = [[] for i in range(n)]

for i in range(m):
    l, r, d = map(int, input().split())
    l-=1;r-=1
    edge[l].append((r, d))
    edge[r].append((l, -d))

flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf:
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

# 2文字の連続部分列はN-1個なので、N-1個のBooleanの配列を生成
b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]

for _ in range(Q):
    l,r = map(int,input().split())
    # bのl番目からr-1番目までの和を出力
    print(sum(b[l-1:r-1]))

### FIXED CODE ###

import itertools

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

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

for _ in range(Q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])
### BUGGY CODE ###

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

res = 1
for i in range(1, n):
    if min(p[:i]) < p[i]:
        continue
    else:
        res += 1

print(res)

### FIXED CODE ###

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

res = 1
m = p[0]
for i in range(1, n):
    if m < p[i]:
        continue
    else:
        res += 1
        m = p[i]

print(res)
### BUGGY CODE ###

# -*- coding:utf-8 -*-

def solve():
    N, Q = list(map(int, input().split(" ")))
    S = input()
    L, R = [], []
    for i in range(Q):
        l, r = list(map(int, input().split(" ")))
        L.append(l)
        R.append(r)
    
    for i in range(Q):
        s = S[L[i]-1:R[i]]

        ans = 0
        if len(s) < 2:
            print(ans)
            continue
        
        for i in range(0, len(s)-1):
            if s[i]+s[i+1] == "AC":
                ans += 1
        print(ans)


if __name__ == "__main__":
    solve()

### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve():
    N, Q = list(map(int, input().split(" ")))
    S = input()
    L, R = [], []
    for i in range(Q):
        l, r = list(map(int, input().split(" ")))
        L.append(l)
        R.append(r)
    
    # 累積話で解く
    accumulations = [0] * N

    for i in range(1, N):
        if S[i-1]+S[i] == "AC":
            accumulations[i] = accumulations[i-1] + 1
        else:
            accumulations[i] = accumulations[i-1]

    for i in range(Q):
        if L[i]-1 == 0:
            print(accumulations[R[i]-1])
            continue
        else:
            print(accumulations[R[i]-1] - accumulations[L[i]-1])
            continue


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

# 73

MOD = 10**9 + 7
x, y = map(int, input().split())

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = finv_l[i-1] * inv_l[i]


def ncr(n, r):
    return (((fac_l[n] * finv_l[r]) % MOD) * finv_l[n-r]) % MOD


if a % 3 != 0 or b % 3 != 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))


### FIXED CODE ###

# 73

MOD = 10**9 + 7
x, y = map(int, input().split())

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = (finv_l[i-1] * inv_l[i]) % MOD

def ncr(n, r):
    return (fac_l[n] * (finv_l[r] * finv_l[n-r]) % MOD) % MOD


if a % 3 != 0 or b % 3 != 0 or a < 0 or b < 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))

ans = "YES"

for p in t:
    if p in d:
        i = d.index(p)
        d[i] = 0
    else:
        ans = "NO"
        break

print(ans)

### FIXED CODE ###

n = int(input())
d = input().split()
m = int(input())
t = input().split()

dic = dict()

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di] = 1

ans = "YES"
for ti in t:
    if ti not in dic or dic[ti] == 0:
        ans = "NO"
        break
    else:
        dic[ti] -= 1

print(ans)