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

H,W = list(map(int,input().split()))

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

path = [[[] for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])
M_checked[0][0]=True
while len(Q)>0:
    i,j=Q.pop()
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            M_checked[i][j]=True
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)

### FIXED CODE ###


H,W = list(map(int,input().split()))

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

path = [[[] for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])
M_checked[0][0]=True
while len(Q)>0:
    i,j=Q.pop()
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            M_checked[p[0]][p[1]]=True
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)
### BUGGY CODE ###

from collections import Counter
n=int(input())
l=[]
for i in range(n):
    s=input()
    l.append(Counter(s))
ans=0

for i in range(n):
    for j in range(n):
        if i<j:
             if l[i]==l[j]:
                 ans+=1
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
l={}
ans=0
for i in range(n):
  s=input()
  ss=sorted(s)
  s="".join(ss)
  ans+=l.setdefault(s, 0) 
  l[s]+=1
print(ans)
### BUGGY CODE ###

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]
def main():
    N,K = map(int,input().split())
    *A, = map(int,input().split())
    SA = cumulative_sum(A)
    B = {}

    for i in range(N):
        for j in range(i+1,N+1):
            s = SA.get(i,j)
            B[s] = B.get(s,0)+1

    ans = 0
    for i in range(40,-1,-1):
        x = ans + (1<<i)
        c = sum(n for b,n in B.items() if b&x==x)
        if c>=K:ans = x
    print(ans)
main()

### FIXED CODE ###

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]
def main():
    N,K = map(int,input().split())
    *A, = map(int,input().split())
    SA = cumulative_sum(A)
    B = {}

    for i in range(N):
        for j in range(i+1,N+1):
            s = SA.get(i,j)
            B[s] = B.get(s,0)+1

    ans = 0
    for i in range(40,-1,-1):
        x = ans + (1<<i)
        c = sum(n for b,n in B.items() if b&x==x)
        if c>=K:ans = x
    print(ans)
main()
### BUGGY CODE ###

def main():
    n = int(stdinput())

    d = MyDict()

    for _ in range(n):
        cmd, value = stdinput().split()
        if cmd == 'insert':
            d.insert(value)
        elif cmd == 'find':
            if d.find(value):
                print('yes')
            else:
                print('no')

class MyDict():
    def __init__(self):
        self.E = []
    
    def insert(self, value):
        self.E.append(value)
    
    def find(self, value):
        return value in self.E

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')


### FIXED CODE ###

def main():
    n = int(stdinput())

    st = [None] * (4**12)

    for _ in range(n):
        cmd, value = stdinput().split()
        if cmd == 'insert':
            st[get_hash(value)] = 1
        elif cmd == 'find':
            if st[get_hash(value)] == 1:
                print('yes')
            else:
                print('no')

CODES = {'A' : 1, 'C' : 2, 'G' : 3, 'T' : 4}
def get_hash(s):
    base = 1
    h = 0
    for c in s:
        code = CODES[c]
        h += code * base
        base *= 4
    return h

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')
### BUGGY CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		for z in [None]*Q:
			if e[0] > d:
				if cont == True:
					if mini < 1000000001:
						print(mini)
					else:
						print(-1)
				else:
					mini = min(kouho)
					if mini < 1000000001:
						print(mini)
					else:
						print(-1)
			else:
				break
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    m = 0
    for i in range(n):
        m += int(s[-1-i])*(10**(i))
        mp = m % p
        mod[mp] += 1
    for m in mod:
        ans += m*(m+1)//2

print(ans)

### FIXED CODE ###

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        m10 = (10 * m10) % p
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

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

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
data=[[] for i in range(N+1)]
lst=set()
for a,b in AB:
    data[a].append(b)
    lst.add(b)

st=list(set(range(1,N))-lst)[0]
stack=deque([st])
lst=[0 for i in range(N+1)]
while stack:
    a=stack.popleft()
    for p in data[a]:
        lst[p]=a
        stack.append(p)

for i in range(1,N+1):
    print(lst[i])


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
data=[[] for i in range(N+1)]
lst=set()
came=[set() for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    lst.add(b)
    came[b].add(a)

st=list(set(range(1,N))-lst)[0]
stack=deque([st])
lst=[0 for i in range(N+1)]


while stack:
    a=stack.popleft()
    for p in data[a]:
        came[p].remove(a)
        if not came[p]:
            lst[p]=a
            stack.append(p)

for i in range(1,N+1):
    print(lst[i])
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
A = [input() for _ in range(H)]
m = [[float('inf')] * W for _ in range(H)]


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    while queue:
        p, q = queue.popleft()
        if 0 < p and A[p - 1][q] == '.' and m[p - 1][q] > m[p][q] + 1:
            m[p - 1][q] = m[p][q] + 1
            queue.append((p - 1, q))
        if 0 < q and A[p][q - 1] == '.' and m[p][q - 1] > m[p][q] + 1:
            m[p][q - 1] = m[p][q] + 1
            queue.append((p, q - 1))
        if p < H - 1 and A[p + 1][q] == '.' and m[p + 1][q] > m[p][q] + 1:
            m[p + 1][q] = m[p][q] + 1
            queue.append((p + 1, q))
        if q < W - 1 and A[p][q + 1] == '.' and m[p][q + 1] > m[p][q] + 1:
            m[p][q + 1] = m[p][q] + 1
            queue.append((p, q + 1))


for i, s in enumerate(A):
    for j, c in enumerate(s):
        if c == '#':
            m[i][j] = 0
            bfs(i, j)
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '#' else 3000 for c in input()] for _ in range(H)]
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)
### BUGGY CODE ###

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

arr = []
ans = 0

for i in range(N+1):
    y = i
    while y >= 1:
        arr.append(int(i % 10))
        i /= 10
    if sum(arr)>= A and sum(arr) <= B:
        ans += i
        arr = []
    else:
        arr = []
        
print(ans)



### FIXED CODE ###


N, A, B = map(int,input().split())
ans = 0
arr = []
for y in range(N+1):
	i = y
	while i >= 1:
		arr.append(int(i % 10))
		i /= 10
	if sum(arr) <= B and sum(arr) >= A:
		ans += y
		arr = []
	else:
		arr = []

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


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import numpy as np

N, M, Q = map(int, input().rstrip().split(' '))

memo = np.zeros((N, N)).astype(int)

for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    memo[:p, q-1:] += 1

for i in range(Q):
    p, q = map(int, input().rstrip().split(' '))
    print(memo[p-1][q-1])


### FIXED CODE ###

# coding: utf-8
# Your code here!

N, M, Q = map(int, input().rstrip().split(' '))

count = [[0] * (N + 1) for _ in range(N+1)]
memo = [[0] * (N + 1) for _ in range(N+1)]

for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    count[p][q] += 1

for i in range(1,N+1):
    for j in range(1,N+1):
        memo[i][j] = count[i][j] + memo[i-1][j] + memo[i][j-1] - memo[i-1][j-1]

for i in range(Q):
    p, q = map(int, input().rstrip().split(' '))
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])
### BUGGY CODE ###

n = int(input())

def culc(number):
    count = 0
    num = int(number ** 0.5)
    for i in range(1, num+1):
        for j in range(1, num+1):
            for k in range(1, num+1):
                tmp = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
                if tmp == number:
                    count += 1
    return count

for i in range(1, n+1):
    if i < 6:
        print(0)
    elif i == 6:
        print(1)
    else:
        print(culc(i))



### FIXED CODE ###

n = int(input())
ans = [0] * 1030302

for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            number = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            ans[number] += 1


for x in range(1, n+1):
    print(ans[x])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    S = input().strip()
    ans = 0
    while 1:
        c = S.count("ABC")
        if c == 0:
            break
        else:
            ans += c
            S = S.replace("ABC", "BCA")
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    S = input().strip()
    S = S.replace("BC","D")
    ans = 0
    a = 0
    for c in S:
        if c == "A":
            a += 1
        elif c == "D":
            ans += a
        else:
            a = 0
        
    print(ans)

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

K, S = map(int,input().split())
p = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                p += 1
print(p)

### FIXED CODE ###

K, S = map(int,input().split())
p = 0
for x in range(K+1):
    if S-x <= 2*K:
        for y in range(min(S-x+1,K+1)):
            if S-x-y <= K:
                p += 1
print(p)
### BUGGY CODE ###

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

# tmp1 = A[-1] - A[0]
# tmp2 = A[-1] - (20 - A[0] - A[-1])
# tmp2 = A[-1] - A[1]

# print(min(tmp1, tmp2))
# # print(A[-1]-A[0])

# ans = []
ans = -1
for i in range(N):
    tmp = 0
    I = A[i]
    for j in range(N-1):
        index = i + j + 1
        if index >= N:
            index -= N
        J = A[index]
        if I < J:
            tmp += J - I
        else:
            tmp += K - I + J
        # print(I,J, tmp)
        I = J
    if ans == -1:
        ans = tmp
    elif ans > tmp:
        ans = tmp
    # ans.append(tmp)
print(ans)
# print(ans)
# print(min(ans))

### FIXED CODE ###

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

# tmp1 = A[-1] - A[0]
# tmp2 = A[-1] - (20 - A[0] - A[-1])
# tmp2 = A[-1] - A[1]

# print(min(tmp1, tmp2))
# # print(A[-1]-A[0])

# ans = []
ans = -1
for i in range(N):
    # 右方向
    tmp = A[-1] - A[i]
    if i != 0:
        tmp += K - A[-1] + A[i-1]
    
    if ans == -1:
        ans = tmp
    elif ans > tmp:
        ans = tmp
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
A = input().split()

s = []
for i in range(N):
    if i == 0:
        s.append(A.count('1'))
    else:
        s.append(A.count(str(i+1)))
for i in s:
    print(i)

### FIXED CODE ###

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

count = []
for i in range(len(A)+1):
    count.append(0)
for i in range(len(A)):
    count[A[i]-1] += 1

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

N,K=map(int,input().split())
H=[0]+[int(h) for h in input().split()]
dp = [999999999 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 0
dp[2] = abs(H[2] - H[1])
for i in range(3, N + 1):
    if i-K < 1:
        starter=1
    else:
        starter=i-K

    lists=[dp[i]]+[dp[x]+abs(H[x]-H[i]) for x in range(starter,i)]

    dp[i] = min(lists)


print(dp[N])



### FIXED CODE ###

N,K=map(int,input().split())
H=[0]+[int(h) for h in input().split()]
dp = [999999999 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 0
dp[2] = abs(H[2] - H[1])
for i in range(3, N + 1):
    if i-K < 1:
        starter=1
    else:
        starter=i-K

    lists=[dp[i]]+[dp[x]+abs(H[x]-H[i]) for x in range(starter,i)]

    dp[i] = min(lists)


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

import sys
sys.setrecursionlimit(1000000)

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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)

prev = [None for _ in range(n)]
dist = [float('inf') for _ in range(n)]


def dfs(start, d):
    if dist[start] < d:
        return
    for n_r in edge[start]:
        if dist[n_r] > d + 1:
            dist[n_r] = d + 1
            prev[n_r] = start
        else:
            continue
        dfs(n_r, d + 1)


dist[0] = 0
dfs(0, dist[0])
if None in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)


### FIXED CODE ###

import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)
### BUGGY CODE ###

def fact(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact
def combinations_count(n, r):
    return fact(n) // (fact(n - r) * fact(r))

ab = input().split()
a, b = int(ab[0]), int(ab[1])
sum=a+b
if sum % 3==0:
	n=int(sum/3)
	m=b-n
	print(int(combinations_count(n, m))%(10**9+7))
else:
	print("0")

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result % (10 ** 9 + 7)
ab = input().split()
a, b = int(ab[0]), int(ab[1])
sum = a + b
if a>(2*b) or b>(2*a):
	print("0")
elif sum % 3 == 0:
    n = int(sum / 3)
    m = b - n
    print(cmb(n, m))
else:
	print("0")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    s = input()
    ll = [0]*n
    rl = [0]*n
    lr = []

    for i in range(n):
        ll[i] = s[:i + 1].count("AC")
        rl[i] = s[i:].count("AC")

    for i in range(q):
        l, r = map(int, input().split())
        l = max(l - 1, 0)
        lr.append([l , r - 1])

    for i, j in lr:
        ans = rl[0] - ll[i] - rl[j]
        print(ans)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    s = input()
    t = [0]*(n + 1)

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

main()
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
k = max(N,M)
l = min(N,M)
N = k
M = l
mod = 10**9+7
def frac(N):
    ans = 1
    for i in range(2,N+1):
        k = i % mod
        ans *= k
    return ans
if N - M > 1:
    print(0)
    exit()
if N == M:
    F = frac(N)
    f = F * F % mod
    print((2*f) % mod)
    exit()
if N == M+1:
    F1 = frac(M)
    F2 = frac(N)
    print((F1*F2) % mod)
    exit()


### FIXED CODE ###

N,M = [int(i) for i in input().split()]
k = max(N,M)
l = min(N,M)
N = k
M = l
mod = 10**9+7
def frac(N):
    ans = 1
    ans1 = 1
    ans2 = 1
    ans3 = 1
    for i in range(2,N+1):
        if i % 3 == 0:
            ans1 *=i
            ans1 %= mod
        if i % 3 == 1:
            ans2 *=i
            ans2 %= mod
        if i % 3 == 2:
            ans3 *=i
            ans3 %= mod
    ans = ans1*ans2*ans3 % mod
    return ans
if N - M > 1:
    print(0)
    exit()
if N == M:
    F = frac(N)
    f = F * F % mod
    print((2*f) % mod)
    exit()
if N == M+1:
    F1 = frac(M)
    F2 = frac(N)
    print((F1*F2) % mod)
    exit()
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
m = 10**15
for i in set(l):
  m = min(m,sum(abs(j-i) for j in l))
print(m)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
import statistics as st
m = int(st.median(l))
print(sum(abs(m-i) for i in l))