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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n, x, y = map(int,input().split()) #n:頂点数　w:辺の数
w = n
ans = [0 for _ in range(n-1)]
# print(ans)
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w-1):
    # x,y = map(int,input().split())
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

# print(dijkstra(0,n,w,cost))
for i in range(n-1):
    aa = dijkstra(i, n, w, cost)
    # print(aa)
    for j in range(i+1, n):
        ans[aa[j]] += 1
ans = ans[1:] + [0]
# print(*ans)
for A in ans:
    print(A)

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0 for _ in range(n-1)]
for i in range(1, n):
    for j in range(i+1, n+1):
        d = min(j-i, abs(x-i) + abs(y-j) + 1)
        ans[d-1] += 1

print(*ans, sep='\n')
### BUGGY CODE ###

a=int(input())
ans=0
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)
for i in range(1,a+1):
    for j in range(1,a+1):
        for k in range(1,a+1):
            ans+=gcd(i,j,k)
print(ans)

### FIXED CODE ###

a=int(input())
import math
print(sum(math.gcd(math.gcd(i,j),k)for i in range(1,a+1) for j in range(1,a+1) for k in range(1,a+1)))
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
  a.sort()
  a[-1] //= 2
print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
  a_min = heapq.heappop(a)
  heapq.heappush(a,(-1)*(-a_min // 2))
print(-sum(a))
### BUGGY CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)
a = [-1]*10000
a[0] = 0
a[1] = 1

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

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

from collections import defaultdict


def get_data(data_dic, num, check_data):
    for i in range(len(data_dic))[::-1]:
        if data_dic[i][0] == num:
            check_data.add(data_dic[i])
            data_dic.pop(i)
        elif data_dic[i][1] == num:
            data_add = (data_dic[i][1], data_dic[i][0], data_dic[i][2])
            check_data.add(data_add)
            data_dic.pop(i)
    return check_data, data_dic


def main():
    num = int(input())


    data_dic = [tuple(map(int, input().split())) for i in range(num - 1)]
    parent_data = [-1 for i in range(num + 1)]
    dist_data = [0 for i in range(num + 1)]

    check_data_now, data_dic = get_data(data_dic, 1, set())
    check_data_next = set()

    while len(check_data_now) > 0:
        parent_list = set()
        for u, v, w in check_data_now:
            parent_data[v] = u
            dist_data[v] = w % 2
            parent_list.add(v)


        for ele in parent_list:
            check_data_next, data_dic = get_data(data_dic, ele, check_data_next)
        check_data_now = check_data_next
        check_data_next = set()


    for i in range(1, num + 1):
        now_data = i
        dist = 0

        while parent_data[now_data] != -1:
            dist += dist_data[now_data]
            now_data = parent_data[now_data]
        if dist % 2 == 0:
            print(0)
        else:
            print(1)








if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys


def visit(current, v, dist, color):
    for ele in v[current]:
        if color[ele] != -1:
            continue
        if dist[(ele, current)] % 2 == 0:
            color[ele] = color[current]
        else:
            if color[current] == 0:
                color[ele] = 1
            else:
                color[ele] = 0
        visit(ele, v, dist, color)

def main():
    sys.setrecursionlimit(100100)
    num = int(input())

    v = [[] for i in range(num + 1)]

    dist = {}

    for i in range(1, num):
        a, b, d = map(int, input().split())
        v[a].append(b)
        v[b].append(a)
        dist[(a, b)] = d
        dist[(b, a)] = d

    color = [-1 for i in range(num + 1)]
    color[1] = 0
    visit(1, v, dist, color)

    for i in range(1, num + 1):
        print(color[i])

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

n=int(input())
'''
import sys
sys.setrecursionlimit(1000000)
def kaijo(n):
    if n==0:
        return(1)
    else:
        n=n%(10**9+7)
        return(n*kaijo(n-1))
print(kaijo(n)%(10**9+7))
'''
ans=1
for i in range(1,n+1):
    ans*=i%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
'''
import sys
sys.setrecursionlimit(1000000)
def kaijo(n):
    if n==0:
        return(1)
    else:
        n=n%(10**9+7)
        return(n*kaijo(n-1))
print(kaijo(n)%(10**9+7))
'''
ans=1
for i in range(1,n+1):
    ans=i*(ans%(10**9+7))
print(ans%(10**9+7))
### BUGGY CODE ###

import itertools


def main():
    n, m = map(int, input().split())

    X = list(map(int, input().split()))
    Y = list(map(int, input().split()))

    s = 0
    for x in itertools.combinations(X, 2):
        for y in itertools.combinations(Y, 2):
            x_len = x[0] - x[1]
            y_len = y[0] - y[1]
            s += x_len * y_len

    print(s % (10 ** 9 + 7))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools


def main():
    n, m = map(int, input().split())

    x = list(map(int, input().split()))
    y = list(map(int, input().split()))

    x_len = 0
    y_len = 0

    for i in range(n):
        x_len += (2 * i - n + 1) * x[i] % (10 ** 9 + 7)
        # print(x_len)

    for j in range(m):
        y_len += (2 * j - m + 1) * y[j] % (10 ** 9 + 7)
        # print(y_len)

    print(x_len * y_len % (10 ** 9 + 7))


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

N = int(input())

counts = [0] * 10001
for i in range(1, 311):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            result = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            if result > 10000:
                continue
            if i == j and j == k:
                counts[result] += 1
            elif i == j or j == k:
                counts[result] += 3
            else:
                counts[result] += 6

for n in range(1, N + 1):
    print(counts[n])

### FIXED CODE ###

N = int(input())

counts = [0] * 10001
for i in range(1, 101):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            result = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            if result > 10000:
                continue
            if i == j and j == k:
                counts[result] += 1
            elif i == j or j == k:
                counts[result] += 3
            else:
                counts[result] += 6

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

N = int(input())
A = list(map(int,input().split()))
B = [[0 for i in range(len(A))] for j in range(len(A))]
for i in range(len(A)):
    for j in range(i+1,len(A)):
        B[i][j] = A[i]^A[j]

ans = 0
for i in range(len(A)):
    ans += sum(B[i])
bk = int(1e9+7)
ans = ans%bk
print(ans)

### FIXED CODE ###

import numpy as np 

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

A = np.array(A,np.int64)##Ai<2^60

ans = 0
mod = int(1e9+7)

for i in range(60+1):
    bottom_bit = (A>>i)&1 ##i回シフトしたときの最下位bit
    ones = np.sum(bottom_bit[bottom_bit>0])
    ##ans += (N-ones)*ones*(2**i) ##0の個数*1の個数*2^i個
    tmp = ones*(N-ones)
    for j in range(i):
        tmp = (tmp * 2) % mod
    ans += tmp

print(ans%mod)
### BUGGY CODE ###

# ABC158 D
s=input()
q=int(input())
l=[]

for i in range(q):
    l.append(list(map(str,input().split())))
# print(l)
t_str=s
for ll in l:
    if ll[0]=='1':
        t_str=t_str[::-1]
    elif ll[0]=='2':
        if ll[1]=='1':
            t_str=ll[2]+t_str
        elif ll[1]=='2':
            t_str+=ll[2]
print(t_str)


### FIXED CODE ###

# ABC158 D
from collections import deque
s=input()
q=int(input())
l=[]

for i in range(q):
    l.append(list(map(str,input().split())))

cnt=0
front_str=''
end_str=''

t_str=deque(s)
front_str=deque(front_str)
end_str=deque(end_str)

for ll in l:
    if ll[0]=='1':
        cnt+=1
    elif ll[0]=='2':
        if cnt%2==0:
            if ll[1]=='1':
                front_str.appendleft(ll[2])
            elif ll[1]=='2':
                end_str.append(ll[2])
        elif cnt%2==1:
            if ll[1]=='1':
                end_str.append(ll[2])
            elif ll[1]=='2':
                front_str.appendleft(ll[2])
ans=list(front_str)+list(t_str)+list(end_str)

if cnt%2==0:
    ans=''.join(ans)
else:
    ans=ans[::-1]
    ans=''.join(ans)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    ## 1の位からi+1文字のうち13で割ったもののあまりがjであるものの数
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in range(0,10):
                # ?がjのときの追加されるあまり
                addmod = (j*10**(i-1))%13
                for k in range(0,13):
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]
        else:
            addmod = (int(S[N-i])*10**(i-1))%13
            for k in range(0,13):
                modmod = (k+addmod)%13
                dp[i][modmod] += dp[i-1][k]

    print(dp[N][5]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    ## 1の位からi+1文字のうち13で割ったもののあまりがjであるものの数
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    list10 = range(0,10)
    list13 = range(0,13)
    keta =1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in list10:
                addmod = j*keta%13
                for k in list13:
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]%MOD
        else:
            addmod = (int(S[N-i])*keta)%13
            for k in list13:
                modmod = (k+addmod)%13
                dp[i][modmod] = dp[i-1][k]%MOD
        keta*=10
        keta%=13
    print(dp[N][5]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

import sys

N,K,Q=map(int,sys.stdin.readline().split())
A=[int(sys.stdin.readline())-1 for i in range(Q)]

for j in range(N):
    if K+A.count(j)>Q:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
p = 10 ** 9 + 7
#二項定理(nCr)を高速に計算する
def cmb(n,r,p):
    N = 10 ** 5 + 5 #必要なサイズを指定
    fact = [1,1]
    factinv = [1,1]
    inv = [0,1]
    for i in range(2,N+1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1] % p))

    if (r < 0) or (n < r):
        return 0
    r = min(r,n-r)
    return fact[n] * factinv[r] * factinv[n-r] % p

A_max = 0
A_min = 0
for i in range(N-K+1):
    A_max = (A_max + (A[(K-1)+i] * cmb((K+i-1),i,p))) % p   
    A_min = (A_min + (A[-1*(K+i)] * cmb((K+i-1),i,p))) % p
    #print(A_max,A_min,cmb((K+i),i,p))
ans = (A_max - A_min)
if ans < 0:
    ans = p + ans
ans %= p
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
mod = p = 10 ** 9 + 7

fact = [1]
fact_inv = [1]
for i in range(10**5+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
 
 
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod    

A_max = 0
A_min = 0
for i in range(N-K+1):
    A_max = (A_max + (A[(K-1)+i] * mod_comb_k((K+i-1),i,p))) % p   
    A_min = (A_min + (A[-1*(K+i)] * mod_comb_k((K+i-1),i,p))) % p
    #print(A_max,A_min,cmb((K+i),i,p))
ans = (A_max - A_min)
if ans < 0:
    ans = p + ans
ans %= p
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(x) for x in input().split()]
B = [[A[i], i] for i in range(N)]
B.sort()
C = []
cnt = 0
for b, i in B:
  p = bisect.bisect(C, i)
  l = (i - C[p - 1]) if p else (i + 1)
  r = (C[p] - i) if p < len(C) else (N - i)
  C = C[:p] + [i] + C[p:]
  cnt += b * l * r
print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0] * (N + 1)
for i in range(N):
  B[A[i]] = i + 1
L = list(range(N + 2))
R = list(range(N + 2))
cnt = 0
for i in range(N, 0, -1):
  l = L[B[i]]
  r = R[B[i]]
  cnt += i * (B[i] - l + 1) * (r - B[i] + 1)
  L[r + 1] = l
  R[l - 1] = r
print(cnt)
### BUGGY CODE ###

import collections 
_ = input()
a = [*map(int, input().split())]
q = int(input())
b = [[*map(int,input().split())] for _ in range(q)]
c = collections.Counter(a)
for i,j in b:
    if j not in c:
        c[j] = 0
    if i not in c:
        c[i] = 0
    c[j]+=c[i]
    c[i] = 0
    print(sum(k*v for k,v in c.items()))

### FIXED CODE ###

import collections
_ = input()
a = [*map(int, input().split())]
q = int(input())
s = sum(a)
b = [[*map(int,input().split())] for _ in range(q)]
c = collections.Counter(a)
for i,j in b:
    if j not in c:
        c[j] = 0
    if i not in c:
        c[i] = 0
    s += (j-i)*c[i]
    c[j]+=c[i]
    c[i] = 0
    print(s)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0]
ans = a[1]-a[0]
for i in range(n-1):
  if a[i] <= nowmin:
    k = max(a[i+1:]) - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]
    
print(ans)



### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0]
nowmax = max(a[1:])
ans = nowmax - nowmin
for i in range(n-1):
  if a[i] == nowmax:
    nowmax = max(a[i+1:])
  if a[i] < nowmin:
    k = nowmax - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]


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

N = int(input())
leng = 10**6+1
memo = [0]*leng
li = []
for n in map(int, input().split()):
    x = 0
    li.append(n)
    while x < leng:
        memo[x] +=1
        x += n
count = 0
for n in li:
    if memo[n] == 1:
        count+=1
print(count)

### FIXED CODE ###

N = int(input())
leng = 10**6+1
memo = [0]*leng
li = []
for n in map(int, input().split()):
    x = 0
    li.append(n)
    if memo[n] >1:
        pass
    else:
        while x < leng:
            memo[x] +=1
            x += n
count = 0
for n in li:
    if memo[n] == 1:
        count+=1
print(count)
### BUGGY CODE ###

import bisect

A, B, Q = map(int, input().split())
INF = float('inf')
s = [- INF] + [int(input()) for i in range(A)] + [INF]
t = [- INF] + [int(input()) for i in range(B)] + [INF]

for i in range(Q):
    x = int(input())
    b, d = bisect.bisect_left(s, x), bisect.bisect_left(t, x)
    ans = INF
    for S in [s[b-1], s[b]]:
        for T in [t[d-1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            ans = min(ans, d1, d2)
    print(ans)

### FIXED CODE ###

import bisect

A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [- INF] + [int(input()) for i in range(A)] + [INF]
t = [- INF] + [int(input()) for i in range(B)] + [INF]

for i in range(Q):
    x = int(input())
    b, d = bisect.bisect_left(s, x), bisect.bisect_left(t, x)
    ans = INF
    for S in [s[b-1], s[b]]:
        for T in [t[d-1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            ans = min(ans, d1, d2)
    print(ans)
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    a,b,c = readInts()
    MaxArea = a * b * c
    red = 0
    dist = MaxArea - red
    for i in range(1,MaxArea//(a*b)//2 + 1):
        #print(red)
        red += a * b
        dist = min(dist,abs(MaxArea - red - red))
    print(dist)
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    A = sorted(readInts())
    a,b,c = A
    #MaxArea = a * b * c
    #red = 0
    #dist = MaxArea - red
    # for i in range(1,MaxArea//(a*b)//2 + 1):
    #     #print(red)
    #     red += a * b
    #     dist = min(dist,abs(MaxArea - red - red))
    #print(dist)
    print(abs(a*b*(c//2+c%2) - a*b*(c//2)))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

a, b, x = map(int, input().split())
i = 0
s = 0
while a > x*i:
    i = i + 1 
while b - (x*i + x*s) >= 0:
    s = s + 1
print(s)

### FIXED CODE ###

a, b, x = map(int, input().split())
#b以下で小さくかつbに最も近いxの倍数 x*i (x*i=0を含める)
i = b // x
#aより小さくかつaに最も近いxの倍数 x*j (x*j=0を含める)
j = (a-1) // x
print(i-j)
### BUGGY CODE ###

x = input().split() 
n,q = int(x[0]), int(x[1]) 
a = input()
for i in range(q):
  y = input().split() 
  l,r = int(y[0]),int(y[1]) 
  x = a[l-1:r]
  print(x.count('AC')) 

### FIXED CODE ###

n,q = map(int, input().split())  
a = input() 
l = [0]*n; 

for i in range(2,n+1):
    x = a[(i-2):i]
    l[i-1] = l[i-2]
    if x=='AC':
        l[i-1] += 1

for i in range(q):
  le,ri = map(int, input().split())  
  print(l[ri-1]-l[le-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N):
    B.append(A.index(i+1)+1)
C = map(str, B)
D = " ".join(C)
print(D)
    
    

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*N
for i, j in enumerate(A):
    B[j-1] = i+1
print(*B)
### BUGGY CODE ###

N = int(input())

P_list = []
M_list = []


for i in range(N):
    if i == N-1:
        P_list.append(1)

    else:
        P_list.append(i+2)


for i in range(N):
    M_list.append((i+1) % P_list[i])

print(sum(M_list))

### FIXED CODE ###

N = int(input())

mod_sum = N*(N-1)//2
print(mod_sum)

#りゅうせいの解答2 不正解2つあり
# N = int(input())
#
# mod_sum = int(N*(N-1)/2)
# print(mod_sum)

# りゅうせいの解答1　実行時間超過
#  N = int(input())
#
# P_list = []
# M_list = []
#
#
# for i in range(N):
#     if i == N-1:
#         P_list.append(1)
#
#     else:
#         P_list.append(i+2)
#
#
# for i in range(N):
#     M_list.append((i+1) % P_list[i])
#
# print(sum(M_list))