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

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

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




distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i-1)//n, (i-1) % n) for i in p]
ans=0
for i,j in p:
    ans+=distance[j][i]
    d = deque()
    d.append((j, i, distance[j][i]))
    check[j][i] = 0
    while len(d):
        x, y, dis = d.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if 0 <= nx < n and 0 <= ny < n:
                # 更新できるマスは更新
                if distance[nx][ny] > dis:
                    distance[nx][ny] = dis
                    d.append((nx, ny, dis + check[nx][ny]))

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

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

import bisect


def main():
    n = int(input())
    l_lst = list(map(int, input().split()))
    l_lst.sort()

    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):

            lst = l_lst[j + 1:]
            a = l_lst[i]
            b = l_lst[j]
            count += bisect.bisect_left(lst, a + b)

    print(count)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect


def main():
    n = int(input())
    l_lst = list(map(int, input().split()))
    l_lst.sort()

    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):

            a = l_lst[i]
            b = l_lst[j]
            tmp = bisect.bisect_left(l_lst, a + b)
            tmp -= j + 1
            tmp = max(0, tmp)
            count += tmp

    print(count)


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

n,q=map(int,input().split())
s=str(input())
l=[]
r=[]
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)#文字列の最初
    r.append(b)#文字列の最後

ans=[]

for i in range(n-1):
    if s[i:i+2]=="AC":
        ans.append(1)
    else:
        ans.append(0)
    

for i in range(q):
    print(sum(ans[l[i]-1:r[i]-1]))


#print(s[2:7])=ACTAC

### FIXED CODE ###

n,q=map(int,input().split())
s=str(input())
l=[]
r=[]
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)#文字列の最初
    r.append(b)#文字列の最後

ans=[]
ans.append(0)
count=0
for i in range(n-1):
    if s[i:i+2]=="AC":
        count+=1
        ans.append(count)
    else:
        ans.append(count)

for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])


#print(s[2:7])=ACTAC
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
 
for x in range(k+1):
  for y in range(x,k+1):
    for z in range(y,k+1):
      if x + y + z == s:
        if x == y == z:
          ans += 1
        elif x == y or y == z:
          ans += 3
        else:
          ans += 6
          
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if 0 <= s - i - j <= k:
      ans += 1
      
print(ans)
### BUGGY CODE ###

from collections import Counter
import numpy as np

N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = 2**np.arange(63,-1,-1) % mod

count = np.zeros(64,dtype=int) 
for i in range(N):
  b = list(map(int, list(bin(A[i])[2:])))
  b = np.array([0]*(64-len(b))+b)
  count += b

print((base*count*(N-count)).sum() % mod)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = [(2**i)%mod for i in range(63,-1,-1)]

count = [0 for i in range(64)]
for i in range(N):
  b = list(map(int, list(bin(A[i])[2:])))
  b = [0]*(64-len(b))+b
  for j in range(64):count[j]+=b[j]

print(sum([base[i]*count[i]*(N-count[i]) for i in range(64)])%mod)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

H, W, D = [int(x) for x in input().split()]
A = [(-1, -1)] * 100000

for y in range(H):
    tmp = [int(x) for x in input().split()]
    for x, e in enumerate(tmp):
        A[e] = (x, y)

Q = int(input())
LR = [[int(e) for e in input().split()] for i in range(Q)]

for start, goal in LR:
    place = start
    point = 0

    while place != goal:
        placeX, placeY = A[place]
        nxtX, nxtY = A[place + D]

        point += (abs(nxtX - placeX) + abs(nxtY - placeY))
        place += D
    print(point)


### FIXED CODE ###

H, W, D = [int(x) for x in input().split()]
size = H*W+1
c = [(-1, -1)] * size
p = [0] * size

for y in range(H):
    for x, a in enumerate([int(s) for s in input().split()]):
        c[a] = (x, y)

for a in range(D+1, size):
    p[a] = p[a-D] + abs(c[a][0] - c[a-D][0]) + abs(c[a][1] - c[a-D][1])

Q = int(input())
for i in range(Q):
    L, R = [int(lr) for lr in input().split()]
    print(p[R] - p[L])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
from fractions import gcd
from functools import reduce

def GCD_LCM(A:list, N:int):
    GCD = A[0]
    LCM = A[0]
    for i in range(1,N):
        GCD = gcd(GCD,A[i])
        LCM = (LCM * A[i]) // gcd(LCM, A[i])
    return GCD,LCM

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    MOD = 10**9+7

    GCD, LCM = GCD_LCM(A,N)
    ans = 0
    MAXA = max(A)
    if GCD != 1 and LCM == MAXA:
        for i in range(N):
            ans = (ans + MAXA // A[i]) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM // A[i]) % MOD

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
from functools import reduce

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    MOD = 10**9+7

    GCD = gcd_list(A)
    LCM = lcm_list(A) % MOD
    ans = 0
    if GCD != 1 and LCM == A[-1]:
        for i in range(N):
            ans = (ans + A[-1] * mod_inv(A[i],MOD)) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM * mod_inv(A[i],MOD)) % MOD

    print(ans)

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

mod = 10**9+7

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

s = list(map(int,input().split()))

s.sort()

s = [None] + s

dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1] = [i % s[1] for i in range(m+1)]

for i in range(2,n+1):
    for j in range(m+1):
        dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j%s[i]]) % mod
print(dp[n][m])

### FIXED CODE ###

mod = 10**9+7

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

s = list(map(int,input().split()))

s.sort()

s = [None] + s

dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1] = [i % s[1] for i in range(m+1)]

for i in range(2,n+1):
    for j in range(m+1):
        dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j%s[i]]) % mod
print(dp[n][m])
### BUGGY CODE ###

n = int(input())
s = list(str(input()))

ans = 0
for i in range(1,n-1):
    sr = 0
    sg = 0
    sb = 0
    er = 0
    eg = 0
    eb = 0

    for j in range(i):
        if s[j] != s[i]:
            if s[j] == "R":
                sr += 1
            elif s[j] == "G":
                sg += 1
            else:
                sb += 1
        pass
    for j in range(i+1,n):
        if s[j] != s[i]:
            if s[j] == "R":
                er += 1
            elif s[j] == "G":
                eg += 1
            else:
                eb += 1
    ans += sr*eb + sr*eg + sg*eb + sg*er + sb*er + sb*eg
    for j in range(min(i,n-i-1)):
        if s[i+j+1] != s[i-j-1] and s[i+j+1] != s[i] and s[i] != s[i-j-1]:
            ans -= 1
    # print(i,ans)

print(ans)

### FIXED CODE ###

n = int(input())
s = list(str(input()))

ans = 0
for i in range(1,n-1):
    sr = 0
    sg = 0
    sb = 0
    er = 0
    eg = 0
    eb = 0

    for j in range(i):
        if s[j] != s[i]:
            if s[j] == "R":
                sr += 1
            elif s[j] == "G":
                sg += 1
            else:
                sb += 1
        pass
    for j in range(i+1,n):
        if s[j] != s[i]:
            if s[j] == "R":
                er += 1
            elif s[j] == "G":
                eg += 1
            else:
                eb += 1
    ans += sr*eb + sr*eg + sg*eb + sg*er + sb*er + sb*eg
    for j in range(min(i,n-i-1)):
        if s[i+j+1] != s[i-j-1] and s[i+j+1] != s[i] and s[i] != s[i-j-1]:
            ans -= 1
    # print(i,ans)

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

N = int(input())
ret = int(N * (N - 1) / 2)

zantei = 0

for i in range(1, N + 1):
	if N % i > i - 1:
		zantei = max(zantei, N % i - (i - 1))
		
print(zantei + ret)

### FIXED CODE ###

N = int(input())

print(N * (N - 1) // 2)
### BUGGY CODE ###

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

A = []
B = []
count = 0

for i in range(Q):
    k = input()
    if k == "1":
        count += 1
    else:
        if k[2] == "1":
            if count % 2 == 0:
                A = A + [k[4]]
            else:
                B = B + [k[4]]
        else:
            if count % 2 == 1:
                A = A + [k[4]]
            else:
                B = B + [k[4]]

if count % 2 == 0:
    A.reverse()
    S = A + S + B
else:
    B.reverse()
    S.reverse()
    S = B + S + A

print(*S, sep="")

### FIXED CODE ###

S = input()
Q = int(input())
 
A = ""
B = ""
count = 0

Que = []
ope = []

def rev(s):
    re = ""
    for i in range(len(s)):
        re = re + s[len(s) - 1 - i]
    return re
 
for i in range(Q):
    k = input()
    if k == "1":
        count += 1
        Que.append("1")
        ope.append("0")
    else:
        Que.append("2")
        ope.append([k[2],k[4]])
 
cou = 0
 
if count % 2 == 0:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = ope[i][1] + A
            else:
                B = B + ope[i][1]
else:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = A + ope[i][1]
            else:
                B = ope[i][1] + B
 
if count % 2 == 0:
    S = A + S + B
else:
    S = rev(S)
    S = B + S + A
 
print(S)
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = None

for i in range(0, N - K + 1):
    s = sum(a[i:i+K]) + K

    if ans is None or ans < s:
        ans = s

print(ans/2)

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = None
s = None

for i in range(0, N - K + 1):
    s = sum(a[i:i+K]) + K if s is None else s - a[i - 1] + a[i + K - 1]

    if ans is None or ans < s:
        ans = s

print(ans/2)
### BUGGY CODE ###

N, A = list(map(int, input().split(' ')))
x = list(map(int, input().split(' ')))
X = max(x)
X = max(X, A)

dp = [[[0 for s in range(N * X + 1)] for k in range(N + 1)] for j in range(N + 1)]

dp[0][0][0] = 1
for j in range(N + 1):
    for k in range(N + 1):
        for s in range(N * X + 1):
            if j >= 1 and s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]
#print(dp)
count = 0
for k in range(1, N + 1):
    #print(dp[N][k][k * A])
    count += dp[N][k][k * A]
print(count)

### FIXED CODE ###

N, A = list(map(int, input().split(' ')))
x = list(map(int, input().split(' ')))
X = max(x)
X = max(X, A)

dp = [[[0 for s in range(N * X + 1)] for k in range(N + 1)] for j in range(N + 1)]

dp[0][0][0] = 1
for j in range(1, N + 1):
    for k in range(N + 1):
        for s in range(N * X + 1):
            if s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]
#print(dp)
count = 0
for k in range(1, N + 1):
    #print(dp[N][k][k * A])
    count += dp[N][k][k * A]
print(count)
### BUGGY CODE ###

n,m = map(int,raw_input().split())
xy = [map(int,raw_input().split()) for i in range(n)]
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	print sum(1 for x,y in xy if x1<=x<=x2 and y1<=y<=y2)

### FIXED CODE ###

import bisect
inf = 1e10
n,m = map(int,raw_input().split())
xy = [map(int,raw_input().split()) for i in range(n)]
X = sorted([i[0] for i in xy] + [-inf-1] + [inf+1])
Y = sorted([i[1] for i in xy] + [-inf-1] + [inf+1])

s = [[0]*(n+10) for i in range(n+10)]
for i in range(n):
	a = bisect.bisect_left(X,xy[i][0])
	b = bisect.bisect_left(Y,xy[i][1])
	s[a][b] += 1

for i in range(n+2):
	for j in range(n+2):
		s[i+1][j+1] += s[i+1][j] + s[i][j+1] - s[i][j]

for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1) - 1
	y1 = bisect.bisect_left(Y,y1) - 1
	x2 = bisect.bisect_left(X,x2+1) - 1
	y2 = bisect.bisect_left(Y,y2+1) - 1
	print s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
### BUGGY CODE ###

a,b,k=map(int,input().split())
if k>b-a:
    for i in range(a,b+1):
        print(i)
else:
    l=[]
    s=set()
    for i in range(a,b+1):
        l.append(i)
    for i in range(k):
        s.add(l[i])
        s.add(l[-i-1])
    s_l=list(s)
    s_l.sort()
    for i in range(len(s_l)):
        print(s_l[i])

### FIXED CODE ###

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

ans=list(range(a,min(a+k,b)))+list(range(max(a,b-k+1),b+1))
ans=set(ans)
ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

from collections import deque, Counter, defaultdict
from functools import lru_cache
from itertools import permutations
from heapq import (
    heappush,
    heappop,
    heapreplace,
    heappushpop,
    heapify,
    merge,
    nlargest,
    nsmallest,
)
from statistics import mean, median, mode


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split(" ")))

clcm = 1
for num in a:
    clcm = lcm(clcm, num)

tot = 0
for num in a:
    tot = (tot + clcm // num) % 1000000007

print(tot)


### FIXED CODE ###

def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)

def lcm(a,b):
  return a * b // gcd(a,b)

n = int(input())
av = list(map(int, input().split(' ')))
alcm = 1
for i in av:
  alcm = lcm(alcm, i)

tot = 0
for i in range(n):
  tot += alcm // av[i]

print(tot % 1000000007)
### BUGGY CODE ###

n,k = map(int,input().split())
if k == 0:
    print(n**2)
else:
    r = n//k
    ans = 0
    for i in range(1,r+3): #a=(i-1)×b+あまり
        genkai = n - (i)*k
        for j in range(1,n-k+1): #b=k+j
            x = (i-1)*j
            ans += min(max(genkai-x+1,0),j)
    print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
if k == 0:
    print(n**2)
elif k <= 100:
    ans = 0
    for j in range(k):
        for i in range(k+1,n+1):
            ans += (n-j)//i
    print((n-k+1)*(n-k)-ans)
else:
    r = n//k
    ans = 0
    for i in range(1,r+3): #a=(i-1)×b+あまり
        genkai = n - (i)*k
        for j in range(1,n-k+1): #b=k+j
            x = (i-1)*j
            ans += min(max(genkai-x+1,0),j)
    print(ans)
### BUGGY CODE ###

# coding: utf-8
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n = int(input())
ans = 0
for i in range(n):
    tmp = make_divisors(i + 1)
    ans = ans + (1 + i) * len(tmp)
print(ans)


### FIXED CODE ###

# coding: utf-8
n_input = int(input())
ans = 0
for i in range(1, n_input + 1):
    n = n_input // i
    ans += n * (1 + n) * i // 2
print(ans)
### BUGGY CODE ###

S=raw_input()
 
M=10**9+7
 
a=0
ab=0
ans=0
all=1
 
for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3
 
	ans%=M
	ab%=M
	a%=M
	all%M
 
 
print ans%M

### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in sorted(list(d.keys()))[::-1]:
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+d[y]
print(ans)

### FIXED CODE ###

n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
S=[]
for i in range(L, R):
  for j in range(i+1, R+1):
    s= (i*j) % 2019
    S.append(s)
    
print(min(S))



### FIXED CODE ###

L,R=map(int, input().split())
#2019の倍数が入っていれば０→R-Lが２０１９以上
if R-L>=2019:
    print(0)
    exit()

ans=2019
for i in range(L,R):
    for j in range(i+1,R+1):
        ans=min(ans, (i*j)%2019)
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import Counter
import collections
import numpy as np 
from scipy import sqrt, power, exp, log10
from scipy.fftpack import fft, ifft, fftfreq
import tarfile
import re
import os
import glob
from datetime import datetime
import time
import numpy.linalg as LA
 
round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
for i in range(b):
    r,l = list(map(int,input().split()))
    S1 = S[r-1:l]
    n = S1.count(sub)
    print(n)

### FIXED CODE ###

import numpy as np
from collections import Counter
import collections
import numpy as np 
from scipy import sqrt, power, exp, log10
from scipy.fftpack import fft, ifft, fftfreq
import tarfile
import re
import os
import glob
from datetime import datetime
import time
import numpy.linalg as LA

round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
l = np.zeros(len(S)+1)
for i in range(len(S)):
  l[i+1] = l[i] + (1 if S[i:i+2]=="AC" else 0)

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

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [[0 for j in range(13)] for i in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    num = int(s[0])
    dp[0][num] = 1

for i in range(1, n):
    if s[i] == '?':
        for m in range(10):
            num = (m * 10**i) % 13
            for j in range(13):
                dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod
    else:
        num = (int(s[i]) * 10**i) % 13
        for j in range(13):
            dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod

print(dp[n-1][5])

### FIXED CODE ###

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [[0 for j in range(13)] for i in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    num = int(s[0])
    dp[0][num] = 1

mul = 1
for i in range(1, n):
    mul = (mul*10) % 13
    if s[i] == '?':
        for m in range(10):
            num = (m * mul) % 13
            for j in range(13):
                dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod
    else:
        num = (int(s[i]) * mul) % 13
        for j in range(13):
            dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod

print(dp[n-1][5])
### BUGGY CODE ###

N=int(input())
S=[input() for i in range(N)]
S.sort(key=len)

VLIST=[[set() for j in range(len(S[i]))] for i in range(N)]

for i in range(N):
    for j in range(len(S[i])):
        VLIST[i][j]=VLIST[i][j-1]|{S[i][j]}

# ing木

Next_node_id=[[-1]*26] # "a"～"z"それぞれについて、対応する次のノードのid
Parent_id=[-1] # 親ノード
End=[[]] # そのノードを終端とするStringがあるか

ANS=0

Nodes_id=1
for i in range(N):
    S2=S[i]
    L=len(S2)

    NOW=0
    for j in range(L-1,-1,-1):
        for s in End[NOW]:
            if s in VLIST[i][j]:
                ANS+=1

        if j==0:
            End[NOW].append(S2[0])
            continue
        
        NEXT=ord(S2[j])-97
        
        if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
            Next_node_id[NOW][NEXT]=Nodes_id

            Next_node_id.append([-1]*26)
            Parent_id.append(NOW)
            End.append([])

            NOW=Nodes_id         
            Nodes_id+=1

        else: # 追加しない場合
            NOW=Next_node_id[NOW][NEXT]

print(ANS)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
S=[input().strip() for i in range(N)]
S.sort(key=len)

VLIST=[[set() for j in range(len(S[i]))] for i in range(N)]

for i in range(N):
    for j in range(len(S[i])):
        VLIST[i][j]=VLIST[i][j-1]|{S[i][j]}

# ing木

Next_node_id=[[-1]*26] # "a"～"z"それぞれについて、対応する次のノードのid
Parent_id=[-1] # 親ノード
End=[[]] # そのノードを終端とするStringがあるか

ANS=0

Nodes_id=1
for i in range(N):
    S2=S[i]
    L=len(S2)

    NOW=0
    for j in range(L-1,-1,-1):
        for s in End[NOW]:
            if s in VLIST[i][j]:
                ANS+=1

        if j==0:
            End[NOW].append(S2[0])
            continue
        
        NEXT=ord(S2[j])-97
        
        if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
            Next_node_id[NOW][NEXT]=Nodes_id

            Next_node_id.append([-1]*26)
            Parent_id.append(NOW)
            End.append([])

            NOW=Nodes_id         
            Nodes_id+=1

        else: # 追加しない場合
            NOW=Next_node_id[NOW][NEXT]

print(ANS)
### BUGGY CODE ###

[A,B,K] = list(map(int,input().split()))
for i in range(0,K):
    if A>=1:
        A-=1
    else:
        if B>=1:
            B-=1
        else:
            continue
print(A,B)

### FIXED CODE ###

[A,B,K] = list(map(int,input().split()))

if A<=K:
    K = K-A
    A = 0
    if B>=K:
        B=B-K
    else:
        B=0
    
else:
    A=A-K

print(A,B)