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

import collections
import math

def combinations_count(n, r):
    if n < 2:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a_list = list(map(int, input().split()))
a_col = collections.Counter(a_list)
c_dic = {}
sm = sum([c * (c - 1) for c in a_col.values()]) // 2

for a in a_list:
    if a in c_dic:
        print(c_dic[a])
    else:
        ans = sm - combinations_count(a_col[a], 2) + combinations_count(a_col[a] - 1, 2)
        print(ans)
        c_dic[a] = ans

### FIXED CODE ###

import collections
import math

def combinations_count(n, r):
    if n < 2:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a_list = list(map(int, input().split()))
a_col = collections.Counter(a_list)
c_dic = {}
sm = sum([c * (c - 1) for c in a_col.values()]) // 2
for a in a_list:
    if a in c_dic:
        print(c_dic[a])
    else:
        ans = sm - combinations_count(a_col[a], 2) + combinations_count(a_col[a] - 1, 2)
        print(ans)
        c_dic[a] = ans
### BUGGY CODE ###

ans = 0

def dfs(idx, N, choice, tot):
    if idx == N:
        global ans
        if choice > 0 and choice*A == tot:
            ans += 1
        return

    dfs(idx + 1, N, choice + 1, tot + x[idx])
    dfs(idx + 1, N, choice, tot)

N, A = map(int, input().split())
x = [int(i) for i in input().split()]

dfs(0, N, 0, 0)

print(ans)

### FIXED CODE ###

import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]

    # 3d DP
    max_x = max(x)

    dp = [[[0] * (max_x * N + 1) for j in range(N + 1)]
                                 for i in range(N + 1)]

    dp[0][0][0] = 1

    for i in range(0, N):
        for k in range(0, N + 1):
            for y in range(max_x * N + 1):
                if dp[i][k][y]:
                    dp[i + 1][k][y] += dp[i][k][y]
                    dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]

            # print(dp[i][k])
        # print()

    cnt = 0
    for k in range(1, N + 1):
        for y in range(1, max_x * N + 1):
            if y // k == A and y % k == 0:
                cnt += dp[N][k][y]

    print(cnt)

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

# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
count = [0] * (max(a) + 1)
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, max(a) + 1, i):
        count[j] = 1
    count[i] = 2

for i in a:
    if count[i] != 1:
        ans += 1

print(ans)


### FIXED CODE ###

# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
m = max(a)
count = [0 for _ in range(m + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, m + 1, i):
        count[j] = 1
    count[i] = 2

for i in a:
    if count[i] != 1:
        ans += 1

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

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
    s=sum(p[i:i+k])+k
    if ans<s:
        ans=s
print(ans/2)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=sum(p[0:k])+k
s=sum(p[0:k])+k
for i in range(1,n-k+1):
    s+=-p[i-1]+p[i+k-1]
    if ans<s:
        ans=s
print(ans/2)
### BUGGY CODE ###

dp = [[0] * 100100 for i in range(110)]

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

for i in range(1, N+1):
    for sum_w in range(W+1):
        if sum_w - w[i-1] >= 0:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1])
        
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])


### FIXED CODE ###

dp = [[0] * 100100 for i in range(110)]

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

for i in range(1, N+1):
    for sum_w in range(W+1):
        if sum_w - w[i-1] >= 0:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-w[i-1]] + v[i-1])
        
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

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

import sys

import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(s, n, sh, sw, gh, gw, c, ans):
    if n == 1:
        ans[sh:gh + 1, sw:gw + 1] = c
        c += 1
        return c
    # Horizontal division
    if s.shape[0] > 1:
        n_ = 0
        for h in range(gh - sh):
            n_ += np.sum(s[sh+h, sw:gw+1])
            if 0 < n_ < n:
                c = dfs(s, n_    , sh        , sw, sh + h, gw, c, ans)
                c = dfs(s, n - n_, sh + (h+1), sw, gh    , gw, c, ans)
                return c
    # Vertical division
    n_ = 0
    for w in range(gw - sw):
        n_ += np.sum(s[sh:gh+1, sw+w])
        if 0 < n_ < n:
            c = dfs(s, n_    , sh, sw        , gh, sw + w, c, ans)
            c = dfs(s, n - n_, sh, sw + (w+1), gh, gw    , c, ans)
            return c


def main():
    H, W, K = map(int, input().split())
    s = [None] * H
    s = np.full(shape=(H, W), fill_value=False, dtype=bool)
    for i in range(H):
        s[i] = [j == "#" for j in input().rstrip()]

    ans = np.zeros(shape=(H, W), dtype=int)
    _ = dfs(s, K, 0, 0, H - 1, W - 1, 1, ans)
    for i in range(H):
        print(" ".join(map(str, ans[i])))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    s = np.zeros(shape=(H, W), dtype=np.bool)
    for i in range(H):
        s[i] = tuple(map(lambda x: True if x == "#" else False, input().rstrip()))

    ans = np.zeros(shape=(H, W), dtype=np.int64)
    h_keep = 0
    k = 1
    for h in range(H):
        if s[h].sum() > 0:
            indices = np.where(s[h])[0]
            ans[h_keep:h + 1] = k
            k += 1
            for idx in reversed(indices[:-1]):
                ans[h_keep:h + 1, :idx + 1] = k
                k += 1
            h_keep = h + 1
        else:
            h_keep = min(h_keep, h)

    if h_keep < H:
        h_base = h_keep - 1
        for h in range(h_keep, H):
            ans[h] = ans[h_base]

    for h in range(H):
        print(" ".join(map(str, ans[h])))


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

import math

x = int(input())
a = 0
while True:
    aa = a ** 5
    bb = aa - x
    bbb = bb ** 0.2
    if bb < 0:
        b = -1
    else:
        b = 1
    b *= int(bbb.real + bbb.imag)
    # print(a,b)
    if aa - b ** 5 == x:
        print(a,b)
        break
    a += 1

### FIXED CODE ###

import math
import sys

x = int(input())
r = math.ceil(x ** 0.2)
# print(r)
def reverse_num(x):
    return r - x
def calc_b(aa):
    bb = aa - x
    bbb = abs(bb) ** 0.2
    if bb < 0:
        b = -1
    else:
        b = 1
    # print(bb,b * int(bbb.real + bbb.imag))
    return b * int(bbb.real + bbb.imag)
def check(a):
    aa = a ** 5
    b = calc_b(aa)
    # print(a,b)
    if aa - b ** 5 == x:
        print(a,b)
        return True
    else:
        return False
for a in range(r // 2 + 1):
    if check(a) or check(reverse_num(a)):
        sys.exit()
a = r + 1
while True:
    if check(a):
        sys.exit()
    a += 1
### BUGGY CODE ###

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


for i in range(1,N+1):
    count=0
    for j in A:
        if i==j:
            count+=1
    print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
counter=[0]*N
for i in A:
    counter[i-1]+=1
print(*counter,sep='\n')
### BUGGY CODE ###

n = int(input())
a = [0] + list(map(int,input().split()))
ans = 0
for i in range(1,n):
    for j in range(i+1,n+1):
        if abs(i-j)==a[i]+a[j]:
            ans += 1
print(ans)

### FIXED CODE ###

import collections
n = int(input())
a = [0] + list(map(int,input().split()))

a_pos = [a[i]+i for i in range(1,n+1)]
a_neg = [-a[i]+i for i in range(1,n+1)]
#print(a_pos)
#print(a_neg)

c_pos = collections.Counter(a_pos)
c_neg = collections.Counter(a_neg)
#print(c_pos)
#print(c_neg)

ans = 0
for c in c_pos:
    ans += c_pos[c] * c_neg[c]

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

from functools import reduce
from operator import mul

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

num = reduce(mul, a[:k])
for i in range(k, n):
    num2 = reduce(mul, a[i-k+1:i+1])
    if num < num2:
        print('Yes')
    else:
        print('No')
    num = num2

### FIXED CODE ###

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

for i in range(k, n):
    if a[i]/a[i-k] > 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from sys import stdin
from collections import deque

N = int(stdin.readline().rstrip())
b = [int(x) for x in stdin.readline().rstrip().split()]
ans = deque([])

while N > 0:
    index = N - 1
    while index >= 0:
        if b[index] == index + 1:
            ans.appendleft(b[index])
            b1 = b[:index]
            b2 = b[index + 1:]
            b = b1 + b2
            N -= 1
            break
        index -= 1

print(*ans)


### FIXED CODE ###

from sys import stdin, exit
from collections import deque

N = int(stdin.readline().rstrip())
b = [int(x) for x in stdin.readline().rstrip().split()]
ans = deque([])

while N > 0:
    index = N - 1
    while index >= 0:
        if b[index] == index + 1:
            ans.appendleft(b[index])
            b1 = b[:index]
            b2 = b[index + 1:]
            b = b1 + b2
            N -= 1
            break
        index -= 1
        if index == -1:
            print(-1)
            exit()

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

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
d=[]
d_len=0
for _ in range(m):
    b,c=map(int,input().split())
    d_len+=b
    for _ in range(b):
    	d.append(c)

d=sorted(d,reverse=True)
right=sum(a)
left=0

for i in range(min(n,d_len)):
    if a[i]<d[i]:
        left+=d[i]
        right-=a[i]
    else:
        break
print(right+left)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
arr=[]

for i in range(m):
    b,c=map(int,input().split())
    arr.append((b,c))

a=sorted(a)
arr=sorted(arr,key=lambda x:-x[1])

flag=0
left=0
for tup in arr:
    for i in range(left,min(left+tup[0],n)):
        if tup[1]>a[i]:
            a[i]=tup[1]
        else:
            flag=-1
            break
        if i==n-1:
            flag=-1
            break
    left+=tup[0]
    if flag==-1:
        break

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

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)
    return len(divisors)

num = int(input())
ans = 0
for i in range(1, num):
  ans += make_divisors(i)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
  ans += (N-1) // a

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

n,m,q=map(int,input().split())
s=[input() for _ in range(n)]
a=[map(int,input().split()) for _ in range(q)]
for k in range(q):
    x1,y1,x2,y2=a[k]
    v=e=0
    for i in range(x1-1,x2):
        for j in range(y1-1,y2):
            if s[i][j]=='1':
                v+=1
                if i!=x2-1 and s[i+1][j]=='1':
                    e+=1
                if j!=y2-1 and s[i][j+1]=='1':
                    e+=1
    print(v-e)

### FIXED CODE ###

n,m,q=map(int,input().split())
s,v,el,eu=([[0]*(m+2) for _ in range(n+2)] for _ in range(4))
for i in range(1,n+1):
    s[i][1:m+1]=map(int,input())
    for j in range(1,m+1):
        v[i][j]=v[i][j-1]+s[i][j]
        el[i][j]=el[i][j-1]+s[i][j]*s[i][j-1]
        eu[i][j]=eu[i][j-1]+s[i][j]*s[i-1][j]
for i in range(2,n+1):
    for j in range(1,m+1):
        v[i][j]+=v[i-1][j]
        el[i][j]+=el[i-1][j]
        eu[i][j]+=eu[i-1][j]
for _ in range(q):
    x1,y1,x2,y2=map(int,input().split())
    print(v[x2][y2]-v[x1-1][y2]-v[x2][y1-1]+v[x1-1][y1-1]
            -(el[x2][y2]-el[x1-1][y2]-el[x2][y1]+el[x1-1][y1])
            -(eu[x2][y2]-eu[x1][y2]-eu[x2][y1-1]+eu[x1][y1-1]))
### BUGGY CODE ###

S = input()
T = input()

import sys
sys.setrecursionlimit(2147483647)

def dfs(i,j):
    if (i,j) in dic: return dic[(i,j)]
    if i > len(S) - 1 or j > len(T) - 1:
        return ""
    ans  = ""
    if S[i] == T[j]:
        ans = S[i] + dfs(i + 1,j + 1)
    else:
        res1 = dfs(i + 1,j)
        res2 = dfs(i, j + 1)
        if max([len(res1),len(res2)]) == len(res1):
            ans = res1
        else:
            ans = res2
    dic[(i,j)] = ans
    return ans
dic = {}
print(dfs(0,0))
    

### FIXED CODE ###

S = input()
T = input()
dp = [[ 0] * (len(S) + 1 ) for _ in range(len(T) + 1)]
ma = 0
for i in range(len(dp)-1):
    for j in range(len(dp[0])-1):
        if T[i ] == S[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
             dp[i + 1][j + 1]  = max(dp[i][j + 1],dp[i +1][j])
i = len(T) - 1
j = len(S) - 1 
ans = ""
while i >=0 and j >= 0:
    if dp[i][j+1] == dp[i + 1][j + 1]:
        i-=1
    elif dp[i + 1][j] == dp[i + 1][j + 1]:
        j-=1
    else:
        #print(j,i)
        ans = S[j] + ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

from functools import lru_cache

n, q = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n-1)]
pxpx = [list(map(int, input().split())) for _ in range(q)]

pxdict = {i:0 for i in range(1, 1+n)}
for p, x in pxpx :
    pxdict[p] += x

babadict = {b:a for a, b in abab}

@lru_cache(maxsize=10**5+1)
def counter(node) :
    if node == 1 :
        return pxdict[1]
    else :
        return pxdict[node]+counter(babadict[node])

for i in range(1, n+1) :
    print(counter(i))

### FIXED CODE ###

from operator import itemgetter
n, q = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n-1)]
pxpx = [list(map(int, input().split())) for _ in range(q)]
abab.sort(key=itemgetter(0))

ans = [0 for _ in range(n)]
for p, x in pxpx :
    ans[p-1] += x
for a, b in abab :
    ans[b-1] += ans[a-1]
print(*ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

lis = [0]*60

for a in A:
    for i in range(60):
        lis[i] += a%2
        a = a //2

ans = 0
for i, j in enumerate(lis):
    ans += j * (N-j) *(2**i)
    ans = ans % (10**9 + 7)

print(ans)

### FIXED CODE ###

N = int(input())
 
lis = [0]*60
 
for a in input().split():
    a = int(a)
    for i in range(60):
        lis[i] += a % 2
        a = a//2
ans = 0
for i, j in enumerate(lis):
    ans += j * (N-j) *(2**i)
    ans = ans % (10**9 + 7)
 
print(ans)
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n
# O(n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)


def chil_pop(l):
    for i in b[l]:
        b[i].pop(b[i].index(l))
        chil_pop(i)

chil_pop(0)

def chil_add(z,x):
    ans[z] += x
    for i in b[z]:
        chil_add(i,x)

for i in range(q):
    p,x = mi()
    chil_add(p-1,x)

ans_str = ''
for i in range(n):
    # print(ans[i],end=' ')
    ans_str = ans_str + str(ans[i]) + ' '
print(ans_str)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
### BUGGY CODE ###

N = int(input())

#文字数分aで埋める
#末尾をbにする
#一桁上の文字+1文字までは許容するルールで増加させていく

import itertools

stop_combination = [chr(i) for i in range(97,97+N)]
combination_list = list(itertools.product(stop_combination, repeat=N))

printed_expression = set()

for combination in combination_list:
    #print(combination,":",end="")

    if list(combination) == stop_combination:
        print(''.join(map(str, combination)))
        break

    character_dict = dict()
    character_number = 0
    alternative_expression = ""

    for character in combination:
        if character not in character_dict:
            character_dict[character] = character_number
            alternative_expression += str(character_number)
            character_number += 1
        else:
            alternative_expression += str(character_dict[character])

    #print(alternative_expression)

    if alternative_expression not in printed_expression:
        print(''.join(map(str, combination)))
        printed_expression.add(alternative_expression)

### FIXED CODE ###

N = int(input())

#文字数分aで埋める
#末尾をbにする
#一桁上の文字+1文字までは許容するルールで増加させていく

ans = [0 for _ in range(N)]
stop = [i for i in range(N)]

def ans_print(ans_list):
    ans = list()
    for a in ans_list:
        ans.append(chr(a+97)) #97でaが出る

    print(''.join(map(str, ans)))
    return 0

def ans_check(ans):
    max_in_ans = 0

    for i in range(1,N):
        if max_in_ans + 1 < ans[i]:
            ans[i-1] += 1
            ans[i] = 0
            return ans_check(ans)
        else:
            max_in_ans = max(max_in_ans,ans[i])
    else:
        return ans

if N == 1:
    print("a")
else:
    while 1:
        ans_check(ans)
        ans_print(ans)
        ans[-1] += 1
        if ans == stop:
            ans_print(ans)
            break
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]
for i in range(1,n):
	p=10**12
	for j in range(k):
		if j>=i:
			break
		else:
			p=min(p,dp[i-j-1]+abs(h[i]-h[i-j-1]))
	dp.append(p)
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]
for i in range(1,n):
	p=10**12
	for j in range(k):
		if j>=i:
			break
		else:
			p=min(p,dp[i-j-1]+abs(h[i]-h[i-j-1]))
	dp.append(p)
print(dp[-1])
### BUGGY CODE ###

k,s = map(int,input().split())
from itertools import product
ans = 0
for x,y,z in product(range(k+1), repeat=3):
    #print(x,y,z)
    if x+y+z == s:
        ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0

'''from itertools import product
for x,y,z in product(range(k+1), repeat=3):
    #print(x,y,z)
    if x+y+z == s:
        ans += 1'''
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            ans +=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import copy
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    for i in range(N):
        Ap = []
        Ap = copy.copy(A)
        del Ap[i]
        print(max(Ap))
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import copy
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    Am = max(A)
    if A.count(Am)>1:
        for j in range(N):
            print(Am)
        return
    Ap = copy.copy(A)
    set(Ap)
    Ap.sort(reverse=True)
    for i in range(N):
        if  A[i] != Am:
            print(Am)
        else:
            print(Ap[1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def travel(x,y,t):
    for i in range(t):
        if x+y==t-2*i:
            return True
    return False
n=int(input())
for i in range(n):
    t, x, y = [int(j) for j in input().split() ]
    if not travel(x,y,t):
        print("No")
        exit()
print("Yes")    


### FIXED CODE ###

n=int(input())
txy=[[0, 0, 0]]+[list(map(int, input().split())) for i in range(n)]
def C(txy0, txy1):
    xx=txy1[1]-txy0[1]
    yy=txy1[2]-txy0[2]
    tt=txy1[0]-txy0[0]
    if xx+yy<=tt and (xx+yy-tt)%2==0:
        return True
    return False
if all(C(txy[i], txy[i+1]) for i in range(n)):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

# ACがある場所の添字（エンド）
# pos_ = []
# last = "x"
# for i, si in enumerate(S):
#     if last == "A" and si == "C":
#         pos_.append(i)
#     last = si
# print(pos_)

import re
pos = [m.start() for m in re.finditer('AC', S)]
# print(pos)

for _ in range(Q):
    l, r = map(int, input().split())
    start = l - 1
    end = r - 1
    # print(start, end)
    count = 0
    for p in pos:
        if start <= p and end >= p + 1:
            count += 1
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

l = [0, 0]
last = S[0]
for i in range(1, len(S)):
    if last == 'A' and S[i] == 'C':
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])
    last = S[i]

for _ in range(Q):
    left, right = map(int, input().split())
    QS.append((left, right))

# print(l)
for left, right in QS:
    ans = l[right] - l[left]
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
ans = N
x = abs(N - K)
if N % K == 0:
    print(0)
else:
    while ans > x:
        ans = x
        x = abs(x - K)
    else:
        print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
ans = N
a = ans // K
b = ans % K

if a > 0:
    ans = N - K * a
    a = ans // K
    b = ans % K

if a  == 0:
    if ans > abs(ans - K):
        print(abs(ans - K))
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
b = [i for i in a if i <= 10**5]
#for i in a:
  #if i > 10**5:
    #break
  #else:
    #b.append(i)
ans = len(a)-len(b)
for i in range(1,10**5+1):
  if b.count(i) == i or 0:
    continue
  elif b.count(i) < i:
    ans += b.count(i)
  elif b.count(i) > i:
    ans += b.count(i)-i
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [i for i in a if i <= 10**5]
ans = len(a)-len(b)
import collections
c = collections.Counter(b)
for i in range(0,10**5+1):
  if c[i] < i:
    ans += c[i]
  if c[i] > i:
    ans += c[i]-i
print(ans)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

count = 0
for i_r in range(0,int(n/r)+1):
#     print('i_r={}'.format(i_r))
    for i_g in range(0,int(n/g)+1):
        if (n - r*i_r - g*i_g)<0:continue
        if 0==((n - r*i_r - g*i_g)%b):
#             print(i_r,i_g)
            count +=1

print(count)


### FIXED CODE ###

a, b, c, n = map(int, input().split())
aa =[a,b,c]
aa.sort()
r = aa[2]
g = aa[1]
b = aa[0]
 
count = 0
for i_r in range(0,int(n/r)+1):
    if (n - r*i_r)<0:continue
    for i_g in range(0,int((n-r*i_r)/g)+1):
        if (n - r*i_r - g*i_g)<0:continue
        if 0==((n - r*i_r - g*i_g)%b):
 
            count = count + 1
 
print(count)
### BUGGY CODE ###

import sys
s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline())
for _ in range(q):
    qi = sys.stdin.readline()
    if len(qi) <= 2:
        s = s[::-1]
    else:
        _,F,C = qi.split()
        if F == "1":
            s = C + s
        else:
            s = s + C           
print(s)

### FIXED CODE ###

from collections import deque

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

t = deque(S)
reverse = False
for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                t.append(C)
            else:
                t.appendleft(C)
        elif F == '2':
            if reverse:
                t.appendleft(C)
            else:
                t.append(C)
result = ''.join(t)
if reverse:
    result = result[::-1]
print(result)