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

S=str(input())
Q=int(input())
which=0#0 normal #1 reverse
check=[list(map(str,input().split())) for i in range(Q)]
front=[]
back=[]
#print(check)
for i in range(Q):
    if check[i][0]=="1":
        which+=1
        which%=2
        continue
    if check[i][0]!="1":
        if which==0:
            if check[i][1]=="1":
                front.insert(0,check[i][2])
            if check[i][1]=="2":
                back.append(check[i][2])
        if which==1:
            if check[i][1]=="1":
                back.append(check[i][2])
            if check[i][1]=="2":
                front.insert(0,check[i][2])
F="".join(front)
B="".join(back)
S=F+S+B
if which==1:
    print("".join(S[len(S)-i-1] for i in range(len(S))))
if which==0:
    print(S)


### FIXED CODE ###

S=str(input())
Q=int(input())
which=0
front=""
back=""
for i in range(Q):
    a=list(map(str,input().split()))
    if a==["1"]:
        which+=1
        which%=2
        continue
    else:
        if which==0:
            if a[1]=="1":
                front=a[2]+front
            if a[1]=="2":
                back+=a[2]
        if which==1:
            if a[1]=="1":
                back+=a[2]
            if a[1]=="2":
                front=a[2]+front

S=front+S+back
if which==1:
    print(S[::-1])
if which==0:
    print(S)
### BUGGY CODE ###

num = int(input())
num2 = list(int(x) for x in input().split())
mb = [0] * num
for i in range(num):
  buka = num2.count(i + 1)
  mb[i] = buka
for j in range(num):
  print(mb[j])

### FIXED CODE ###

num = int(input())
li = list(int(x) for x in input().split())
li2 = [0] * num
num = len(li)
for i in li:
  li2[i - 1] = li2[i - 1] + 1
for j in range(num + 1):
  print(li2[j])
### BUGGY CODE ###

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

a.sort()
b = max(a)
for i in range(0, 31):
    if b < 2**i:
        c = 2**i
        d = i
        break

ref = [2**(i) for i in range(d+1)]
num = []
ama = [0]*len(a)
for i, name in enumerate(a):
    name3 = 0
    for j, name2 in enumerate(ref):
        if name < name2:
            ama[i] += name - name3
            break
        name3 = name2
    num.append(j)

import copy
am = copy.deepcopy(a)
numm = copy.deepcopy(num)
count = m
lenn = len(numm)

while count > 0:
    numm_m = max(numm)
    if numm_m == 0:
         break
    mi = []
    mi_ama = []
    for i, name in enumerate(numm[::-1]):
        if name == numm_m:
            mi.append(lenn-i-1)
            mi_ama.append(ama[lenn-i-1])
    if len(mi) == 1:
        ri = mi[0]
    else:
        mi_ama_max = max(mi_ama)
        ri = mi[mi_ama.index(mi_ama_max)]
    ama[ri] = 0
    numm[ri] -= 1
    am[ri] = am[ri]//2
    count -= 1

print(sum(am))

### FIXED CODE ###

import heapq
import copy
def nint(x):
    return(int(x)*-1)
n, m = list(map(int, input().split()))
a = list(map(nint, input().split()))

b = copy.deepcopy(a)
heapq.heapify(b)

o = heapq.heappop(b)*-1
count = m
while o > 0 and count > 0:
    heapq.heappush(b, (o//2)*-1)
    count -= 1
    o = heapq.heappop(b)*-1

heapq.heappush(b, (o)*-1)

print(sum(b)*-1)
### BUGGY CODE ###

n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=input().split()
    A.append(a)
    B.append(b)
A.reverse()
B.reverse()
A.append(0)
B.append(0)
A=list(map(int,A))
B=list(map(int,B))

v=[0]
for i in range(0,n):
    cnt=0
    if A[i]%B[i]!=0:
        cnt+=(B[i]-A[i]%B[i])
        A[i]+=(B[i]-A[i]%B[i])
    v.append(cnt)
    A[i+1]+= sum(v)
print(sum(v))



### FIXED CODE ###

n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=input().split()
    A.append(a)
    B.append(b)
A.reverse()
B.reverse()
A.append(0)
B.append(0)
A=list(map(int,A))
B=list(map(int,B))

x=0
for i in range(0,n):
    cnt=0
    if A[i]%B[i]!=0:
        cnt+=(B[i]-A[i]%B[i])
        A[i]+=(B[i]-A[i]%B[i])
    x+=cnt
    A[i+1]+= x
print(x)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**7
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append((sh, sw))
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	i, j = q.popleft()
	if i == gh and j == gw:
		print(dist[i][j])
		sys.exit()
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "." and dist[ii][jj] > dist[i][j]:
				dist[ii][jj] = dist[i][j] + 1
				q.append((ii, jj))
			else:
				break
print(-1)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "@":
				break
			if dist[ii][jj] <= dist[i][j]:
				break
			if dist[ii][jj] > dist[i][j] + 1:
				dist[ii][jj] = dist[i][j] + 1
				if ii == gh and jj == gw:
					print(dist[ii][jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
print(-1)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
cnt=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]<l[j]+l[k]:
        cnt+=1
      else:
        break
print(cnt)
      

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
cnt=0
for i in range(n-2):
  a=l[i]
  for j in range(i+1,n-1):
    b=l[j]
    k=bisect.bisect_left(l,a+b)
    cnt+=(k-j-1)
print(cnt)
### BUGGY CODE ###

def main():
  import sys
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  input=sys.stdin.readline
  inf=2**31-1
  n,m=map(int,input().split())
  edge=defaultdict(list)
  used=defaultdict(bool)
  d={}
  l=[]
  for _ in range(m):
    a,b,c=map(int,input().split())
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
  used[1]=True
  edgelist=edge[1]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if used[m[1]]:continue
    d[m[1]]=m[0]
    used[m[1]]=True
    for e in edge[m[1]]:
      if used[e[1]]:continue
      heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
### BUGGY CODE ###

#!/usr/bin/env python3
s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]
for i in range(1, len(s)+1):
    # print(s[len(s)-i:])
    div = (int(s[len(s)-i:]) % mod)
    div_memo[div] += 1

ans = 0
for i in range(len(div_memo)):
    ans += div_memo[i]*(div_memo[i]-1)//2

ans += div_memo[0]
print(int(ans))


### FIXED CODE ###

#!/usr/bin/env python3
s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]

num = 0
d = 1
for n in reversed(s):
    num += int(n)*d
    num %= 2019
    div_memo[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(len(div_memo)):
    ans += div_memo[i]*(div_memo[i]-1)//2

ans += div_memo[0]
print(int(ans))
### BUGGY CODE ###

_ = int(input())
members = input()

counts = []
for i in range(len(members)):
    count = sum([1 for j in range(len(members)) if (members[j] == 'W' and i>j) or (members[j] == 'E' and i<j)])
    counts.append(count)
print(min(counts))

### FIXED CODE ###

n = int(input())
members = input()
m_e = members.count("E")
cost = m_e
costs = []
for i in range(n):
    if members[i]=="E":
        cost-=1
    if (i!=0 and members[i-1]=="W"):
        cost+=1
    costs.append(cost)
print(min(costs))
### BUGGY CODE ###

from sys import stdin
n, k = [int(i) for i in stdin.readline().split(' ')]
h = [int(i) for i in stdin.readline().split(' ')]

minCosts = [0, abs(h[1]-h[0])]
for i in range(2, len(h)):
    minCosts.append(min([abs(h[i]-h[i-j])+minCosts[i-j] for j in range(1, min(i, k)+1)]))

print(minCosts[-1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
K = int(input())
N = len(S)

# MLE対策
if K * 2 >= N-1:
    print(N)
    exit()

dp = [[[0 for _ in range(K+1)] for _ in range(N)] for _ in range(N)]
for i in range(N):
    for k in range(K+1):
        dp[i][i][k] = 1

for _j in range(1, N):
    for i in range(N):
        j = i + _j
        if j < N:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])
                if _j == 1:
                    if S[i] == S[j]:
                        dp[i][j][k] = 2
                    else:
                        if k+1 <= K:
                            dp[i][j][k+1] = 2
                else:
                    if S[i] == S[j]:
                        dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)
                    else:
                        if k+1 <= K:
                            dp[i][j][k+1] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)

print(max(dp[0][N-1]))



### FIXED CODE ###

S = input()
K = int(input())
N = len(S)

# MLE対策
if K * 2 >= N-1:
    print(N)
    exit()

dp = [[[0 for _ in range(K+1)] for _ in range(N)] for _ in range(N)]
for i in range(N):
    for k in range(K+1):
        dp[i][i][k] = 1

for _j in range(1, N):
    for i in range(N):
        j = i + _j
        if j < N:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])
                if _j == 1:
                    if S[i] == S[j]:
                        dp[i][j][k] = 2
                    else:
                        if k+1 <= K:
                            dp[i][j][k+1] = 2
                else:
                    if S[i] == S[j]:
                        dp[i][j][k] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)
                    else:
                        if k+1 <= K:
                            dp[i][j][k+1] = max(dp[i][j][k], dp[i+1][j-1][k] + 2)

print(max(dp[0][N-1]))
### BUGGY CODE ###

def prime_factorization(m: int) -> dict:
    """
    素因数分解
    """
    if m == 1:
        return {1: 1}

    pf = {}
    if m % 2 == 0:
        while m % 2 == 0:
            m //= 2
            pf[2] = pf.get(2, 0) + 1
    p = 3
    while p * p <= m:
        if m % p == 0:
            m //= p
            pf[p] = pf.get(p, 0) + 1
        else:
            p += 2
    if m != 1:
        pf[m] = pf.get(m, 0) + 1
        
    return pf

def get_all_cd(m: int) -> list:    
    """
    全ての約数を探す
    """ 
    def find_cd(m, i, pf_lst, cd_lst):
        """
        割れるかどうかの確認
        """
        if m % i != 0:
            return
        else:
            m //= i
            if m in cd_lst:
                return
            else:
                cd_lst.append(m)
                for i in pf_lst:
                    find_cd(m, i, pf_lst, cd_lst)

    pf = prime_factorization(m)
    cd_lst = [m]
    for i in pf.keys():        
        find_cd(m, i, pf.keys(), cd_lst)    

    return sorted(cd_lst)

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

s_lst = set(get_all_cd(A)) & set(get_all_cd(B))
ans_lst = [1]
for i in s_lst:
    if i == 1:
        continue
    p = prime_factorization(i)
    if len(p) == 1:
        for k, v in p.items():
            if v == 1:
                ans_lst.append(k)
        
print(len(ans_lst))

### FIXED CODE ###

from fractions import gcd

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

m = gcd(A, B)
pf = []
for i in range(2, m+1):
    if i ** 2 > m:
        break
    if m % i == 0:
        pf.append(i)
    while m % i == 0:
        m //= i
if m != 1:
    pf.append(m)
    
print(len(pf) + 1)
### BUGGY CODE ###

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

ans = []
for i in range(Q):
    l, r = map(int, input().split())
    ans.append(S[max(l-1, 0):r].count(AC))

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


### FIXED CODE ###

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

cumsum = [0] * (N + 1)
for i in range(1, N):
    if S[i - 1] == 'A' and S[i] == 'C':
        cumsum[i + 1] = cumsum[i] + 1
    else:
        cumsum[i + 1] = cumsum[i]
for i in range(Q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l])
### BUGGY CODE ###

H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))


### FIXED CODE ###

H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))
### BUGGY CODE ###

import fractions 
import math
from functools import reduce
#最大公約数
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

#インプット
n = int(input())
a = list(map(int,input().split()))

#最大公約数算出
z=lcm_list(a)

print(sum([z//x for x in a])%((10**9)+7))

### FIXED CODE ###

import fractions
 
import math
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
n = int(input())
a = list(map(int,input().split()))

c=0

z=lcm_list(a)

for i in range(0,n):
  c+=(z//a[i])
#print(z)
print(c%((10**9)+7))
### BUGGY CODE ###

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

monsters.sort(reverse=True)
#print(monsters)
ans = min(monsters)

while ans > 0:
    maxnum = max(monsters)
    minnum = min(monsters)
    maxidx = monsters.index(maxnum)

    if maxnum % minnum == 0:
        del monsters[maxidx]
        if len(monsters) == 1:
            print(monsters[0])
            quit()
    else:
        ans = maxnum % minnum
        monsters[maxidx] = ans


### FIXED CODE ###

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

monsters.sort()  # 昇順
minnum = monsters[0]

cnt = len(monsters)
minidx = 0
while cnt > 1:
    for i in range(cnt - 1, 0, -1):
        monsters[i] = monsters[i] % monsters[0]

        if monsters[i] == 0:
            del monsters[i]

        elif monsters[i] == 1:
            print('1')
            quit()

    workmin = min(monsters)
    minidx = monsters.index(min(monsters))
    monsters[minidx] = monsters[0]
    monsters[0] = workmin

    cnt = len(monsters)

print(monsters[0])
### BUGGY CODE ###

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

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))
#print(dls)
#print(drs)

ans = 0
mod = 10**9+7

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?']*power(3, max(0, dls[i]['?']-1), mod))
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?']*power(3, max(0, drs[i]['?']-1), mod))
    ans += (a*b)
    #print(ans)
ans %=mod
print(ans)

### FIXED CODE ###

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

dl = {'A':0, 'C':0, '?':0}
dr = {'A':0, 'C':0, '?':0}

dls = []
drs = []

import copy

for i in range(n):
    if s[i] == 'A' or s[i] == 'C':
        dl[s[i]] += 1
    elif s[i] == 'B':
        dl_ = copy.copy(dl)
        dls.append(dl_)
    else:
        dl_ = copy.copy(dl)
        dls.append(dl_)
        dl[s[i]] += 1
    j = n - 1- i
    if s[j] == 'A' or s[j] == 'C':
        dr[s[j]] += 1
    elif s[j] == 'B':
        dr_ = copy.copy(dr)
        drs.append(dr_)
    else:
        dr_ = copy.copy(dr)
        drs.append(dr_)
        dr[s[j]] += 1

drs = list(reversed(drs))
#print(dls)
#print(drs)

ans = 0
mod = 10**9+7

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

for i in range(len(dls)):
    a = (dls[i]['A']*power(3, dls[i]['?'], mod) + dls[i]['?']*power(3, max(0, dls[i]['?']-1), mod))%mod
    b = (drs[i]['C']*power(3, drs[i]['?'], mod) + drs[i]['?']*power(3, max(0, drs[i]['?']-1), mod))%mod
    ans += (a*b)%mod
    #print(ans)
ans %=mod
print(ans)
### BUGGY CODE ###

from collections import defaultdict


def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


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

dd = defaultdict(int)

for i in range(N):
    dd[A[i]] += 1

count = 0
for k, v in dd.items():
    if v >= 2:
        count += nCr(v, 2)
for i in range(N):
    if dd[A[i]] >= 3:
        ans = count - nCr(dd[A[i]], 2) + nCr(dd[A[i]]-1, 2)
    elif dd[A[i]] == 2:
        ans = count - nCr(dd[A[i]], 2)
    else:
        ans = count
    print(ans)


### FIXED CODE ###

from collections import defaultdict


def calc(x):
    return x*(x-1)//2


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

dd = defaultdict(int)
for i in range(N):
    dd[A[i]] += 1

count = 0
for k, v in dd.items():
    if v >= 2:
        count += calc(v)
for i in range(N):
    ans = 0
    if dd[A[i]] >= 3:
        ans = count - calc(dd[A[i]]) + calc(dd[A[i]]-1)
    elif dd[A[i]] == 2:
        ans = count - 1
    elif dd[A[i]] == 1:
        ans = count
    print(ans)
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)
a = set([])

for i in range(n):
    for j in range(i+1,n+1):
        a.add(s[i:j])
        
b = list(a)
b.sort()
print(b[k-1])

### FIXED CODE ###

from collections import Counter
s = input()
k = int(input())
n = len(s)
bb = Counter(s)
b = list(bb)
b.sort()
a = set([])

for l in range(k):
    for i in range(n):
        if s[i] == b[l]:
            for j in range(5):
                if i + j > n:
                    break
                a.add(s[i:i+1+j])
    if len(a) >= k:
        break
        
b = list(a)
b.sort()
print(b[k-1])
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
count = 0
for i in range(N):
  a = L[i]
  for j in range(i + 1, N):
    b = L[j]
    for k in range(j + 1, N):
      if a + b > L[k] and a + L[k] > b and b + L[k] > a:
        count += 1
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
 
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l,l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
L = N*M//gcd(N,M)
memo = []

for i in range(N):
  memo.append(i*L//N)
for i in range(M):
  tmp = i*L//M
  if tmp in memo:
    if S[tmp//(L//N)] == T[i]:
      continue
    else:
      print(-1)
      exit()
print(L)


### FIXED CODE ###

from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
L = N*M//gcd(N,M)
a = L//N
b = L//M
c = a*b//gcd(a,b)
i = 0
while i<L:
  if S[i//(L//N)] != T[i//(L//M)]:
    print(-1)
    exit()
  i += c
print(L)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p_2 = []
for i in range(n):
    if p[i]%2 == 0:
        p_2.append(p[i]//2+0.5)
    else:
        p_2.append(p[i]//2 + 1)
maxer = 0
for i in range(n-k+1):
    cnt = sum(p_2[i:i+k])
    if cnt >= maxer:
        maxer = cnt
print(maxer)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
maxer = sum(p[:k])
cnt = maxer
st = 0
for i in range(n-k):
    cnt = cnt - p[i] + p[i+k]
    if cnt >= maxer:
        maxer = cnt
        st = i+1
ans = 0
for i in range(st,st+k):
    if p[i]%2 == 0:
        ans += (p[i]//2+0.5)
    else:
        ans += (p[i]//2 + 1)
print(ans)
### BUGGY CODE ###

#AtCorder Beginner Contest 085  C Otoshidama
n, y = map(int, input().split())

a = -1
b = -1
c = -1

for i in range(n + 1):
    if 10000*i == y and i == n:
        a = i
        b = 0
        c = 0
        break
    else:
        for j in range(n-i + 1):
            if i+j == n and 10000*i + 5000*j == y:
                a = i
                b = j
                c = 0
                break
            else:
                for k in range(n - i - j + 1):
                    if  i + j + k == n and 10000*i + 5000*j + 1000*k == y :
                        a = i
                        b = j
                        c = k
                        break


print(str(a) + " " + str(b) + " " + str(c))

### FIXED CODE ###

#AtCorder Beginner Contest 085  C Otoshidama
n, y = map(int, input().split())

a = -1
b = -1
c = -1

for i in range(n + 1):
    if 10000*i == y and i == n:
        a = i
        b = 0
        c = 0
        break
    else:
        for j in range(n - i + 1):
            if i+j == n and 10000*i + 5000*j == y:
                a = i
                b = j
                c = 0
                break
            elif 10000*i + 5000*j + 1000*(n - i -j) == y:
                a = i
                b = j
                c = n - i - j
                break


print(str(a) + " " + str(b) + " " + str(c))
### BUGGY CODE ###

N, Q = input().split()
S = input()
list = []

for i in range(int(Q)):
    list.append(int(x) for x in input().split())

for i in range(int(Q)):
    a, b = list[i]
    sss = S[a - 1:b]
    count = sss.count("AC")
    print(count)
   

### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()

    list = [0] * (N + 1)

    for i in range(N):
        list[i + 1] = list[i] + (1 if S[i:i + 2] == "AC" else 0)

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


if __name__ == '__main__':
    main()