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

def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  friend=[[]for _ in range(n)]
  block=[[]for _ in range(n)]
  for a,b in ab:
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
  for c,d in cd:
    block[c-1].append(d-1)
    block[d-1].append(c-1)
  # 友達連結内でかつ友達でもブロックでもない。
  # 友達連結グループわけ
  ans=[0]*n
  seen=[0]*n
  for t in range(n):
    if seen[t]==1:
      continue
    member=[]
    todo=[t]
    seen[t]=1
    while todo:
      t=todo.pop()
      member.append(t)
      f=friend[t]
      for fi in f:
        if seen[fi]==0:
          todo.append(fi)
          seen[fi]=1
    mn=len(member)
    for m in member:
      ans[m]=mn-len(set(block[m]).intersection(set(member)))-len(friend[m])-1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  gf=[[]for _ in range(n)]
  for a,b in ab:
    gf[a-1].append(b-1)
    gf[b-1].append(a-1)
  gb=[[]for _ in range(n)]
  for c,d in cd:
    gb[c-1].append(d-1)
    gb[d-1].append(c-1)
  seen=[0]*n
  ans=[0]*n
  for i in range(n):
    c=set([i])
    if seen[i]==0:
      todo=[i]
      while todo:
        e=todo.pop()
        l=gf[e]
        for li in l:
          if seen[li]==0:
            todo.append(li)
            seen[li]=1
            c.add(li)
      base=len(c)-1
      for ci in c:
        ans[ci]=base
        for fb in gb[ci]+gf[ci]:
          if fb in c:
            ans[ci]-=1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	lu[i] = i - bitl.Sum(d[i][1])
	ld[i] = i - lu[i]
	bitl.PointAdd(d[i][1], 1)

for i in range(n-1, -1, -1):
	ru[i] = n-1-i - bitr.Sum(d[i][1])
	rd[i] = n-1-i - ru[i]
	bitr.PointAdd(d[i][1], 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += power(n)
	ans -= power(lu[i]+ld[i]) + power(ld[i]+rd[i]) + power(rd[i]+ru[i]) + power(ru[i]+lu[i])
	ans += power(lu[i]) + power(ld[i]) + power(rd[i]) + power(ru[i])
	ans %= MOD

print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)
### BUGGY CODE ###

s = raw_input()
N = len(s)


def judge(x):
    score = 0
    for a, b in zip(s, x):
        if (a, b) == ('p', 'g'):
            score -= 1
        elif (a, b) == ('g', 'p'):
            score += 1
    return score

if N % 2 == 0:
    x  = 'g' * (N / 2) + 'p' * (N / 2)
    score = judge(x)
else:
    score = 0
    for i in xrange(N / 2 + 1):
        x = 'g' * (N / 2) + 'p' * i + 'g' + 'p' * (N / 2 - i)
        score = max(score, judge(x))
print score

### FIXED CODE ###

s = raw_input()
N = len(s)
print N / 2 - s.count('p')
### BUGGY CODE ###

# https://atcoder.jp/contests/abc103/tasks/abc103_d
import sys

def solve():
    pairs.sort(key=lambda pair: pair[1])
    done = set()
    cnt = 0
    i = 0
    while i < m:
        if i in done:
            i += 1
            continue
        _, b0 = pairs[i]
        cnt += 1
        done.add(i)
        for j, (a, _) in enumerate(pairs[i+1:], start=(i+1)):
            if a < b0:
                done.add(j)
    return cnt

n, m = map(int, input().split())
pairs = [tuple(int(c) for c in input().split()) for _ in range(m)]
print(n, pairs, file=sys.stderr)
print(solve())

### FIXED CODE ###

# https://atcoder.jp/contests/abc103/tasks/abc103_d
import sys

def solve():
    pairs.sort(key=lambda pair: pair[1])
    cnt = 0
    base = 0
    for (a, b) in pairs:
        if a >= base:
            cnt += 1
            base = b
    return cnt

n, m = map(int, input().split())
pairs = [tuple(int(c) for c in input().split()) for _ in range(m)]
print(n, pairs, file=sys.stderr)
print(solve())
### BUGGY CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    # j桁目のビットが1であるものの数を記憶
    count_zeros = [0 for j in range(L+1)]
    count_ones = [0 for j in range(L+1)]
    for i in range(N):
        for j in range(L):
            count_ones[j] = count_ones[j] + ((A[i] >> j) & 1)
            count_zeros[j] = N - count_ones[j]
    # A[i] と A[j] (i<j) のxorをとる
    modsum = 0
    for j in range(L):
        base = count_zeros[j] * count_ones[j]
        base = (base<<j) % MOD
        modsum = (base + modsum) % MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

### FIXED CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        P[i].append((A[i], i))
        P[i] = list(set(P[i]))
        P[i].sort()
        P[i] = P[i][-2:]
        for j in range(N):
            if (i & (1 << j)) == 0:
                P[i + (1 << j)] += P[i]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)

func()

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        Ai = A[i]
        Pi = P[i]
        if (Ai, i) > Pi[0]:
            Pi[1] = Pi[0]
            Pi[0] = (Ai, i)
        elif (Ai, i) > Pi[1]:
            Pi[1] = (Ai, i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                Pindex = P[i + (1 << j)]
                for k in range(2):
                    if Pi[k] > Pindex[0]:
                        Pindex[1] = Pindex[0]
                        Pindex[0] = Pi[k]
                    elif Pi[k] > Pindex[1] and Pi[k] != Pindex[0]:
                        Pindex[1] = Pi[k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()
### BUGGY CODE ###

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

Buka_list = []
for i in range(1,N+1,1):
    ninzu = A_list.count(i)
    print(ninzu)
    

### FIXED CODE ###

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

Buka_list = []

for i in range(N):
    Buka_list.append(0)
    
for j in A_list:
    Buka_list[j-1] += 1

for k in range(N):
    print(Buka_list[k])
### BUGGY CODE ###

n, w = map(int, input().split())
dp = [[0 for i in range(w+1)] for j in range(n+1)]
#print (dp)
we = []
v = []
for i in range(n):
	ww,vv = map(int,input().split())
	we.append(ww)
	v.append(vv)
for i in range(n):
	for j in range(w+1):
		if we[i] <= j:
			dp[i+1][j] = max(dp[i][j-we[i]] + v[i], dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]
print (dp[n][w])


### FIXED CODE ###

n, w = map(int, input().split())
dp = [[0 for i in range(w+1)] for j in range(n+1)]
#print (dp)
we = []
v = []
for i in range(n):
	ww,vv = map(int,input().split())
	we.append(ww)
	v.append(vv)
for i in range(n):
	for j in range(w+1):
		if we[i] <= j:
			dp[i+1][j] = max(dp[i][j-we[i]] + v[i], dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]
print (dp[n][w])
### BUGGY CODE ###

N = int(input())
V = list(map(int , input().split()))
C = list(map(int , input().split()))

Benefit = []

for b in range(2**N):
	Binary = []
	binary = b
	for n in range(N):
		Binary.append(binary % 2)
		binary = binary //(2)
#	print("Binary = " + str(Binary))
	B = 0
	for n in range(N):
		if Binary[n] == 1:
			B += V[n] - C[n]
	Benefit.append(B)
#print("Benefit = " + str(Benefit) )
print(max(Benefit))


### FIXED CODE ###

N = int(input())
V = list(map(int , input().split()))
C = list(map(int , input().split()))
B = 0

for n in range(N):
	if V[n] - C[n] > 0:
		B += V[n] - C[n]

print(B)
### BUGGY CODE ###

from heapq import heappush, heappop

def dijkstra_heap(s):
    """頂点sから各頂点への最短距離"""
    d = [float("inf") for _ in range(N)]
    used = [True for _ in range(N)]  # True: 未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, e)
    while len(edgelist):
        min_edge = heappop(edgelist)
        # まだ使われていない頂点の中から最小距離のものを探す
        if not used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist, [e[0]+d[v], e[1]])
    return d

N = int(input())

edge = [[] for _ in range(N)]  # edge[i]: i から出る道の[重み、行き先]の配列

for _ in range(N-1):
    x, y, z = map(int, input().split())
    edge[x-1].append([z, y-1])
    edge[y-1].append([z, x-1])

Q, K = map(int, input().split())
z = dijkstra_heap(K-1)

for _ in range(Q):
    x, y = map(int, input().split())
    print(z[x-1] + z[y-1])


### FIXED CODE ###

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

N = int(input())

edge = [[] for i in range(N)]  # edge[i] : iから出る道の[重み,行先]の配列
for i in range(N-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])

Q, K = map(int, input().split())

zk = dijkstra_heap(K-1)
#print(zk)

for _ in range(Q):
    x, y = map(int, input().split())
    print(zk[x-1] + zk[y-1])
### BUGGY CODE ###

import itertools
n = int(input())
s_list = [input() for _ in range(n)]
res_list = []
for s in itertools.permutations(s_list):
    res_list.append(''.join(s).count('AB'))
print(max(res_list))

### FIXED CODE ###

n = int(input())
s_list = [input() for _ in range(n)]
res_ab = 0
res_ba = 0
res_a = 0
res_b = 0
for s in s_list:
    res_ab += s.count('AB')
    if s[0]=='B' and s[-1]=='A':
        res_ba += 1
    elif s[0]=='B':
        res_a += 1
    elif s[-1] == 'A':
        res_b += 1

if res_ba == 0:
    print(res_ab+min(res_a,res_b))
else:
    if res_a+res_b > 0:
        print(res_ab+res_ba+min(res_a,res_b))
    else:
        print(res_ab+res_ba-1)
### BUGGY CODE ###

a,b,n = map(int,input().split())
ans = 0
for i in range(n+1):
    temp = (a*i)//b - a * (i // b)
    if temp > ans:
        ans = temp
print(ans)

### FIXED CODE ###

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

c = min(b-1,n)
print((a*c)//b - a*(c//b))
### BUGGY CODE ###

S = input()
N = len(S)
ans = 0
T = []
for i in range(N):
    T.append(int(S[i : N]) % 2019)
#T.sort()
ans += T.count(0)
t = set(T)
counted = []
for i in t:
    a = T.count(i)
    if a > 1:
        counted.append(a)
for i in counted:
    ans += i * (i - 1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
N = len(S)
amari = [0 for i in range(2019)]
before = int(S[0])
amari[before] += 1
S = S[1::]
keta = 1
for i in S:
    i = int(i)
    keta = (keta * 10) % 2019
    x = (keta * i + before) % 2019
    amari[x] += 1
    before = x
ans = amari[0]
for i in amari:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())
sl.pop()

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = m = dm = ans = 0
    for i in range(n):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if sl[i] == "D":
            d += 1
        if sl[i] == "M":
            m += 1
            dm += d
        if sl[i] == "C":
            ans += dm

    print(ans)









### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]

stack = deque([[ch-1,cw-1]])
INF=10**8
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
wapu = []
for m in range(-2,3):
    for n in range(-2,3):
        if m!=0 or n!=0:
            wapu += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
    for dx,dy in wapu:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)
### BUGGY CODE ###

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

sorted_l = sorted(l)

for i in range(n):
    tmp = sorted_l.copy()
    tmp.remove(l[i])
    med = tmp[(n-1)//2]
    print(med)


### FIXED CODE ###

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

tmp = l.copy()
tmp.sort()

left = tmp[n//2-1]
right = tmp[n//2]

for item in l:
    if item <= left:
        print(right)
    else:
        print(left)
### BUGGY CODE ###

n = int(input())
S = [input() for i in range(n)]
for i in range(n):
  S[i] = sorted(S[i])
S = sorted(S)
c = 0
for i in range(n - 1):
  j = i + 1
  while S[i] == S[j] and j < n:
    c += 1
    j += 1
    if j == n:
      break
print(c)

### FIXED CODE ###

n = int(input())
S = [input() for i in range(n)]
for i in range(n):
  S[i] = sorted(S[i])
S = sorted(S)
c = 0
i = 0
while i < n - 1:
  j = i + 1
  while j < n:
    if S[i] == S[j]:
      j += 1
    else:
      break
  c += (j-i) * (j-i-1) // 2
  i = j  
print(c)
### BUGGY CODE ###

S = list(input())
Q = int(input())
counter =0

for q in range(Q):
    inpu_ = input()
    if len(inpu_)==1:
        counter += 1
    else:
        a,f,c = map(str,inpu_.split())
        if f=="1":
            if counter%2 == 1:
                S.append(c)
            else:
                S.insert(0,c)

        else:
            if counter%2==1:
                S.insert(0,c)
            else: 
                S.append(c)

if counter%2==1:
    S.reverse()
print("".join(S))


### FIXED CODE ###

S = input()
Q = int(input())
flag = True
from collections import deque
que=deque(S)

for i in range(Q):
    a = input().split()
    if a[0]=="1":
        flag = not flag

    else:
        f = a[1]
        c = a[2]
        if f=="1":
            if flag:
                que.appendleft(c)
            else:
                que.append(c)
        else:
            if flag:
                que.append(c)
            else:
                que.appendleft(c)

if not flag:
    que.reverse()

print("".join(que))
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
from copy import deepcopy
n = int(input())
L = list(map(int,input().split()))
L.sort()
LL = deepcopy(L)
LL.sort(reverse=1)
# print(L,LL)
ans = 0
for i_max,abc_max in enumerate(LL[:-2]):
	ans_bef = ans
	# print("i ",i_max,abc_max)
	for j_mid,abc_mid in enumerate(LL[i_max+1:],i_max+1):
		# print("j ",j_mid,abc_mid)
		# for k_min,abc_min in enumerate(L[j_mid+1:]):
		right = bisect_left(L,abc_max+1-abc_mid)
		# print(right,abc_max+1-abc_mid)
		cur = len(LL[j_mid:-(right+1)])
		if not cur:
			break
		ans += cur
		# print("ans->",ans)
print(ans)

### FIXED CODE ###

from bisect import bisect_left

n =int(input())
L = list(map(int,input().split()))
L.sort()

#L[i]+L[j] > ?
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        zz = L[i]+L[j]
        idx = bisect_left(L,zz)
        ans += idx-j-1
print(ans)
### BUGGY CODE ###

from collections import deque

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = [['' for _ in range(W)] for _ in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            grid[i][j] = line[j]
            if line[j] == '#':
                existing_black_cells += 1

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)): # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x+dx
                Y = y+dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and adjacent not in visited and grid[Y][X] == '.':
                    queue.append(adjacent)
    print(-1)
    return
main()

### FIXED CODE ###

import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()
### BUGGY CODE ###

n,q=[int(i) for i in input().split()]
s=input()
place=tuple(tuple(int(i) for i in input().split()) for _ in range(q))
for i in place:
    l,r=i[0],i[1]
    st=s[l-1:r]
    print(st.count("AC"))

### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
s=input()
AC=deque()
count=0
for i in range(n):
    if i!=0:
        if s[i-1:i+1]=="AC":
            count+=1
    AC.append(count)
for _ in range(q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])