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

import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if union[i] is union[j]:continue
    tmp = union[j].copy()
    while union[j]:
        heapq.heappush(union[i],heapq.heappop(union[j]))
    for k in tmp:
        union[k] = union[i]
    ans += c
    cnt += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)
### BUGGY CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 9, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
inp_offset = n * 2 + 1
for i in range(0, inp[n * 2] * 2, 2):
    u = inp[inp_offset + i]
    l = inp[inp_offset + i + 1]
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            nv = dp_v[i] + v
            if nw > l:
                continue
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for i in range(len(dp_w)):
        nv = dp_v[i] + precalc[u][l - dp_w[i]]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict(int)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

### FIXED CODE ###

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)
### BUGGY CODE ###

def solve():
    from sys import stdin
    from itertools import accumulate
    
    file_input = stdin
    
    N = int(file_input.readline())
    
    img = []
    acc_row = []
    
    for line in file_input:
        line = tuple(map(int, line.split()))
        img.append(line)
        acc_row.append(tuple(accumulate(line)) + (0,))
    
    def acc_list(col):
        return tuple(accumulate(col)) + (0,)
    acc_col = tuple(map(acc_list, zip(*img)))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_row_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_row_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
            
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_row_i_k, img_row_j_k in zip(acc_col[1:], img_row_i[1:], img_row_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_row_i_k + img_row_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()


### FIXED CODE ###

from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    G = tuple(tuple(map(int, line.split())) for line in file_input)
    G1 = tuple(t[1:] for t in G)
    
    # accumulated rows
    ar = ((0,) + tuple(accumulate(line)) for line in G)
    
    # accumulated columns
    ac = ((0,) + tuple(accumulate(line)) for line in zip(*G))
    ac_1 = next(ac)
    ac = tuple(zip(*ac))
    
    ans = 0
    for i, t1 in enumerate(zip(G1, ar, ac, ac_1)):
        G_i, ar_i, ac_i, ac_1i = t1
        ar_ii = ar_i[i]
        for j, t2 in enumerate(zip(G1[i:], ar_i[i+1:], ac[i+1:], ac_1[i+1:]), start=i):
            G_j, ar_ij, ac_j, ac_1j = t2
            single_row = ar_ij - ar_ii
            if single_row > ans:
                ans = single_row
                
            if i == j:
                continue
            
            col_max = ac_1j - ac_1i
            
            for ac_jk, ac_ik, G_ik, G_jk in zip(ac_j, ac_i, G_i, G_j):
                col = ac_jk - ac_ik
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + G_ik + G_jk
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()
### BUGGY CODE ###

n=int(input())
s=input()
dp=[(n+1)*[0]for _ in range(n+1)]
for i in range(1,n):
    for j in range(i+1,n+1):
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        if s[i-1]==s[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        dp[i][j]=min(dp[i][j],j-i)
print(max(max(i)for i in dp))

### FIXED CODE ###

n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
finv = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    finv[i] = pow(p, mod-2, mod)

def comb(n, k):
    return f[n] * finv[n-k] * finv[k] % mod

def count(R,C):
    ret = ((1<<R+C+1)-1) % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = ((1<<C-c)-1) % mod
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = ((1<<R-r)-1) % mod
        ret = (ret-x1*x2) % mod

    return ret

ans = count(r2, c2) + count(r1-1, c1-1) - count(r2, c1-1) - count(r1-1, c2)
ans %= mod
print(ans)

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    #finv[i] = pow(p, mod-2, mod)

finv = [1]*M
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(M-2, 0, -1):
    p = p*(i+1)%mod
    finv[i] = p

g = [0]*M
p = 0
for i in range(1, M):
  g[i] = p = ((p+1)*2-1)%mod

def comb(n, k):
    return f[n] * finv[n-k] * finv[k] % mod

def count(R,C):
    ret = g[R+C+1] % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = g[C-c]
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = g[R-r]
        ret = (ret-x1*x2) % mod

    return ret

ans = count(r2, c2) + count(r1-1, c1-1) - count(r2, c1-1) - count(r1-1, c2)
ans %= mod
print(ans)
### BUGGY CODE ###

from fractions import gcd
K = int(input())
sum = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        d = gcd(a , b)
        for c in range(1, K + 1):
            sum += gcd(d, c)

print(sum)

### FIXED CODE ###

from math import gcd
K = int(input())
sum = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            sum += gcd(a, gcd(b, c))

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

import collections
S=input()[::-1]
l=len(S)
t=0
p=0

ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    ss[p]+=1

for c in ss:
    t+=c*(c-1)//2
print(t)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

n,m=map(int,input().split())
mList=[int(input()) for i in range(m)]
n+=1

#dp=[float("inf")*n]
dp=[0]*n
#dp[0]=0
dp[0]=1
for i in range(1,n):
  #print(i,"に来る方法")
  if i in mList: continue
  dp[i]+=dp[i-1]
  #dp[i]=min(dp[i],dp[i-1]+abs(dp[i]-dp[i-1]))
  if i==1: continue
  dp[i]+=dp[i-2]
  #print(dp[i])
  #dp[i]=min(dp[i],dp[i-2]+abs(dp[i]-dp[i-2]))

print(dp[n-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
mList=set([int(input()) for _ in range(m)])

dp=[0]*(n+1)
dp[0]=1
if 1 not in mList:
  dp[1]=1

for i in range(2,n+1):
  if i in mList: continue
  dp[i]+=dp[i-1]
  dp[i]+=dp[i-2]
  dp[i]%=1000000007

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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()



for i in range(K):
    A_new = [0 for i in range(N)]
    imos_table = [0 for i in range(N)]

    for j in range(N):
        left = max(0, j - A[j])
        right = j + A[j] + 1
        imos_table[left] += 1
        if right >= N:
            pass
        else:
            imos_table[right] -= 1
    
    tmp = 0
    for j in range(N):
        tmp += imos_table[j]
        A_new[j] += tmp

    A = copy.deepcopy(A_new)

print(" ".join(map(str, A)))
    

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

"""
明るさが一定値を超えると計算しなくて良い
一定？d > math.floort(N/2)
"""
if K > 50:
    b = [str(N)] * N
    print(" ".join(b))
    sys.exit()

lamps = [[0 for i in range(N)] for j in range(K + 1)]
lamps[0] = A

"""
累積和〜
"""
for i in range(K):
    if lamps[i] == [N for i in range(N)]:
        ans = [str(N) for i in range(N)]
        print(" ".join(ans))
    tmps = [0 for i in range(N)]
    for j in range(N):
        w = lamps[i][j]
        tmps[max(0, j - w)] += 1
        r = min(N-1, j + w)
        if r + 1 < N:
            tmps[r + 1] -= 1
    hoge = 0
    for j in range(N):
        hoge += tmps[j]
        lamps[i + 1][j] = hoge
ans = lamps[-1]
ans = map(str, ans)
print(" ".join(ans))
### BUGGY CODE ###

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

from collections import Counter
results = Counter(s)

max_key_list = [kv[0] for kv in results.items() if kv[1] == max(results.values())]
for i in sorted(max_key_list):
  print(i)


### FIXED CODE ###

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

from collections import Counter
results = Counter(s)

max_num = results.most_common()[0][1]
max_key_list = [kv[0] for kv in results.items() if kv[1] == max_num]
for i in sorted(max_key_list):
  print(i)
### BUGGY CODE ###

def main():
  N,K= map(int,input().split())
  h = list(map(int,input().split()))

  dp = [0]*N
  dp[0] = 0
  dp[1] = abs(h[0] - h[1])

  for i in range(2,N):
    index = i - K
    if index < 0: index = 0
    ans = 10**9
    for j in range(index,i):
      ans = min(ans,dp[j] + abs(h[i] - h[j]))
    dp[i] = ans
  print(dp[N-1])

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  N,K= map(int,input().split())
  h = list(map(int,input().split()))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i-K,0),i))
  print(dp[N-1])

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    ans += a[i]*sum(a[i+1:])
    ans %= 10**9 + 7
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [i % (10**9 + 7) for i in a]
val = sum(a[1:])
l = [val]
for i in range(1, n):
    val -= a[i]
    l.append(val)
ans = 0
for i in range(n - 1):
    ans += a[i]*l[i]
    ans %= 10**9 + 7
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())

g = {}
steps = 3
for v in range(1,N*steps+1):
    g[v] = []

for _ in range(M):
    u,v = map(int, input().split())
    g[u + N*0].append(v + N*1)
    g[u + N*1].append(v + N*2)
    g[u + N*2].append(v + N*0)

S,T = map(int, input().split())

visiting = [(S,0)]
visited = {}
while visiting:
    v,d = visiting.pop(0)
    if v in visited:
        continue
    visited[v] = d
    if v == T:
        break

    for v2 in g.get(v,()):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,d+1))
if T in visited:
    print(visited[T] // steps)
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
E = {}
for v in range(1,N*3+1):
    E[v] = []
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
dist = [-1 for _ in range(3*N)]
dist[S-1] = 0

q = []
q.append(S)
while q:
    n = q.pop(0)
    if n == T:
        break
    for t in E[n]:
        if dist[t-1] < 0:
            dist[t-1] = dist[n-1] + 1
            q.append(t)
print(-1 if dist[T-1] < 0 else dist[T-1] // 3)
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    a,b,k=map(int,input().split())
    l=[i for i in range(a,b+1)]

    ans=[]
    if k>=b-a+1:
        for i in range(a,b+1):
            print(i)
    else:
        for i in range(a,a+k):
            ans.append(i)
        for j in range(b-k+1,b+1):
            if j not in ans:
                ans.append(j)


        for i in ans:
            print(i)


resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    a,b,k=map(int,input().split())

    ans=[]
    if k>=b-a+1:
        for i in range(a,b+1):
            print(i)
    else:
        for i in range(a,a+k):
            ans.append(i)
        for j in range(b-k+1,b+1):
            if j not in ans:
                ans.append(j)


        for i in ans:
            print(i)


resolve()
### BUGGY CODE ###

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

import bisect

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

Bc, Cc = [0]*n, [0]*n
Bp, Cp = 0, 0

for i in range(n):
    index = bisect.bisect_right(B[Bp:], A[i])
    Bc[i], Bp = n - index - Bp, index + Bp
    index = bisect.bisect_right(C[Cp:], B[i])
    Cc[i], Cp = n - index - Cp, index + Cp

Ccs = [sum(Cc[i:]) for i in range(n)]

count = 0
for bc in Bc:
    if bc > 0:
        count += Ccs[n-bc]

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import bisect
 
n = int(input())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
 
Ac, Cc = [0]*n, [0]*n
# Ap, Cp = 0, 0
 
for i in range(n):
    Ac[i] = bisect.bisect_left(A, B[i])#[Ap:], B[i])
    # Ac[i], Ap = index + Ap, index + Ap
    Cc[i] = n - bisect.bisect_right(C, B[i])#[Cp:], B[i])
    # Cc[i], Cp = n - index - Cp, index + Cp
 
 
count = 0
for i in range(n):
    count += Ac[i]*Cc[i]
 
print(count)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        c = l1[i][1]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)
### BUGGY CODE ###

n,q =map(int,input().split())
s=input()
l=[list(map(int,input().split())) for _ in range(q)]

p=[s[i]+s[i+1]=='AC' for i in range(n-1)]

for i in range(q):
  cnt=sum(p[l[i][0]-1:l[i][1]-1])
  print(cnt)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for _ in range(q)]
a=[0]*n

for i in range(n):
  a[i]=a[i-1]
  if s[i-1:i+1]=='AC':
    a[i]+=1

for i in range(q):
  print(a[l[i][1]-1]-a[l[i][0]-1])
### BUGGY CODE ###

n,x,y=map(int,input().split())
l=[]
r_append = l.append
for i in range(n-1):
  for k in range (i+1,n):
    if k<x-1 or i>y-1:
      r_append(k-i)
    else:
      r_append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
for i in range(1,n):
  print(l.count(i))

### FIXED CODE ###

from collections import Counter
n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for k in range (i+1,n):
      l.append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
S=Counter(l)
for i in range(1,n):
  print(S[i])
### BUGGY CODE ###

import math

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

def solve():
    ans = 0
    sums = [0]
    sum_val = 0
    for i, A_i in enumerate(A):
        sum_val += A_i
        sums.append(sum_val)
    for i in set(sums):
        cnt = sums.count(i)
        if cnt == 1:
            ans += 0
        else:
            ans += (cnt)*(cnt-1)//2
    print(ans)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import collections

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

def solve():
    ans = 0
    sums = [0]
    sum_val = 0
    for i, A_i in enumerate(A):
        sum_val += A_i
        sums.append(sum_val)
    c = collections.Counter(sums)
    for v in c.values():
        ans += (v)*(v-1)//2
    print(ans)


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

from collections import defaultdict, deque

N, M = map(int, input().split())

dic = defaultdict(set)
for _ in range(M):
    A, B = map(int, input().split())
    dic[A].add(B)
    dic[B].add(A)


colors = [0]*(N+1)

def dfs():
    que = deque([(1, 1)])

    while len(que):
        v, color = que.popleft()
        colors[v] = color
        for to in list(dic[v]):
            if (color == colors[to]):
                return False
            if (colors[to] == 0):
                que.append((to, -color))
                
    return True


flag = dfs()
b = colors.count(1)

print(b*(N-b) - M if (flag) else N*(N-1)//2 - M)


### FIXED CODE ###

from collections import defaultdict, deque

N, M = map(int, input().split())

dic = defaultdict(set)
for _ in range(M):
    A, B = map(int, input().split())
    dic[A].add(B)
    dic[B].add(A)


colors = [0]*(N+1)

def dfs():
    que = deque([(1, 1)])

    while len(que):
        v, color = que.popleft()
        colors[v] = color
        for to in list(dic[v]):
            if (color == colors[to]):
                return False
            if (colors[to] == 0):
                que.append((to, -color))
                
    return True


flag = dfs()
b = colors.count(1)

print(b*(N-b) - M if (flag) else N*(N-1)//2 - M)
### BUGGY CODE ###

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

flags = [0] * N
for i in range(N):
    if i != 0 and S[i - 1:i + 1] == 'AC':
        flags[i] = 1
acc_sum = [sum(flags[:i+1]) for i in range(N)]

for i in range(Q):
    l, r = list(map(int, input().split()))
    if l == r:
        print(0)
    else:
        print(acc_sum[r - 1] - acc_sum[l - 1])

### FIXED CODE ###

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

flags = [0] * N
for i in range(N):
    if i != 0 and S[i - 1:i + 1] == 'AC':
        flags[i] = 1

acc_sum = [0] * N
for i in range(1, N):
    if flags[i] == 1:
        acc_sum[i] = acc_sum[i - 1] + 1
    else:
        acc_sum[i] = acc_sum[i - 1]

for i in range(Q):
    l, r = list(map(int, input().split()))
    if l == r:
        print(0)
    else:
        print(acc_sum[r - 1] - acc_sum[l - 1])