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

from itertools import product

N=int(input())
S=input()
t=["0","1","2","3","4","5","6","7","8","9"]

u=product(t,repeat=3)
ans=0
for com in u:
  flag=False
  x=com[0]
  y=com[1]
  z=com[2]
  for i in range(N):
    if S[i]==x:
      for j in range(i+1,N):
        if S[j]==y:
          tmp=S[j+1:]
          if z in tmp:
            flag=True
            break
  if flag:
    ans+=1
print(ans)

### FIXED CODE ###

from itertools import product

N=int(input())
S=list(input())
t=["0","1","2","3","4","5","6","7","8","9"]

u=product(t,repeat=3)
ans=0
for com in u:
  x=com[0]
  y=com[1]
  z=com[2]
  
  if x in set(S):
    idx_x = S.index(x)
    tmp1 = S[idx_x+1:]
    if y in set(tmp1):
      idx_y = tmp1.index(y)
      tmp2 = tmp1[idx_y+1:]
      if z in set(tmp2):
        ans+=1
        continue
        
print(ans)
### BUGGY CODE ###

from collections import defaultdict


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    sum_amount = 0
    dists = []
    dists_comb = defaultdict(int)

    for i in range(len(A)):
        k = 1
        if A[i] == 1:
            dists.append((i, k, k))
        else:
            while A[i] // 2**k > 0:
                dists.append((i, (A[i] // 2**(k - 1) - A[i] // 2**k), k))
                k += 1
    
    dists = sorted(dists, key=lambda x: x[1], reverse=True)
    
    for d in dists:
        if M == 0:
            break
        if dists_comb[d[0]] != 0:
            M -= (d[2] - dists_comb[d[0]])
            dists_comb[d[0]] = d[2]
        else:
            dists_comb[d[0]] = d[2]
            M -= d[2]
    
    if M > 0:
        print(0)
    else:
        for i in range(N):
            sum_amount += A[i] // (2 ** dists_comb[i])
        print(sum_amount)
         

if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
from math import ceil


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

    # As heapq.heappop returns the mininum value of the sequence,
    # we need to multiply -1 in order to attain the maximum
    # value of the sequence.
    A = list(map(lambda x: (-1) * int(x), input().split()))
    heapq.heapify(A)
    for i in range(M):
        heapq.heappush(A, ceil(heapq.heappop(A) / 2))

    print(-sum(A))


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

import numpy as np


def calc_mul4_dp(n, aaa):
    dp = np.array([list(range(16))] * (n + 1), dtype=np.int64)
    arg = np.arange(1, n + 1, dtype=np.int64)

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            dp[i, :-cnt] += dp[i + 1, cnt:]
            dp[i, -cnt:] += dp[i + 1, -1] + arg[:cnt] * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            dp[i, :cnt] += dp[i + 1, 0]
            dp[i, cnt:] += dp[i + 1, :16 - cnt]
        next_a = a
    return dp


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp.T[0] + bdp.T[0]) * 2
    return (mul4dp + np.arange(n + 1)).min()


def test():
    import random
    n = 200000
    aaa = random.choices(range(1, 10 ** 9), k=n)
    print(n)
    print(aaa)
    print(solve(n, aaa))


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

l, r = map(int, input().split())
n = range(l, r+1)
min_x = 2019
for i in range(len(n)-1):
    for j in range(i+1, len(n)):
        cur_x = n[i]*n[j] % 2019
        min_x = min(cur_x, min_x)
        if min_x == 0:
            break
print(min_x)

### FIXED CODE ###

l, r = map(int, input().split())
if l - r >= 2019:
    print(0)
else:
    n = range(l, r+1)
    min_x = 2018
    for i in range(len(n)-1):
        for j in range(i+1, len(n)):
            cur_x = ((n[i]%2019)*(n[j]%2019))%2019
            min_x = min(cur_x, min_x)
            if min_x == 0:
                break
        if min_x == 0:
                break
    print(min_x)
### BUGGY CODE ###

#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  while pre[x] != -1:
    x = pre[x]
  while pre[y] != -1:
    y = pre[y]
  if x != y:
    pre[x] = y
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
print(ans)

### FIXED CODE ###

#解説チラ見
n,m = map(int,input().split())
ans = n
pre = [i for i in range(n)]
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  X = [x]
  while pre[x] != x:
    x = pre[x]
    X.append(x)
  Y = [y]
  while pre[y] != y:
    y = pre[y]
    Y.append(y)
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
# for i in range(p):
#     print(l[i])
s = [[0 for _ in range(n+1)] for _ in range(p)]
for i in range(p):
    for j in range(n):
        s[i][j+1] = s[i][j] + l[i][j]
# for i in range(p):
#     print(s[i])
ans = 0
for j in range(n-1):
    for i in range(p):
        if l[i][j] == 1:
            ans += (2**(p - i - 1)) * ((n - j - 1) - (s[i][n] - s[i][j+1]))
        else:
            ans += (2**(p - i - 1)) * (s[i][n] - s[i][j+1])
        ans = ans % ((10**9) + 7)
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [0 for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            if a_s[c] == '1':
                l[c] += 1
    for i in range(p):
        c1 = l[i]
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

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


import itertools
import math

def main():
    
    input_lines_n = input()
    n = int(input_lines_n)
    xyz_max = 100
    
    for i in range(1, n+1):
        ans = 0
        cnt = 0
        for x, y, z in itertools.product(range(xyz_max), range(xyz_max), range(xyz_max)):
            if x > 0 and y > 0 and z > 0:
                #ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
                ans = (x + y + z)**2 - (x*y + y*z + z*x)
                if ans == i:
                    cnt = cnt + 1
        
        print(cnt)
                    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###


import itertools

def main():
    
    input_lines_n = input()
    n = int(input_lines_n)
    xyz_max = 100
    l = [0] * 10001
    
    for x, y, z in itertools.product(range(xyz_max), range(xyz_max), range(xyz_max)):
        fn = 0
        if x > 0 and y > 0 and z > 0:
            fn = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if fn <= n:
                l[fn] += 1
    
    for i in range(1, n+1):
        print(l[i])
                    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = input()
S = list(input())
min_ = 400000
for i in range(len(S)):
    left = S[:i]
    right = S[i+1:]
    num_change = left.count('W')+right.count('E')
    if num_change < min_:
        min_ = num_change
print(min_)



### FIXED CODE ###

N = int(input())
S = list(input())

change = S[1:].count('E')
min_ = change

for i in range(1, N):
    if S[i-1] == 'W':
        change += 1
    if S[i] == 'E':
        change -= 1
    if change < min_:
        min_ = change
print(min_)
### BUGGY CODE ###

H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]

pre_list = []
# set start point
for iidx, i in enumerate(C):
    for tidx, t in enumerate(i):
        if t == '#':
            pre_list.append((iidx, tidx))
            C[iidx][tidx] = 0

# bfs 
count = 0
 
while len(pre_list) > 0:
    count += 1
    next_list = []
    for y,x in pre_list:
        for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
            if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                continue
            if C[y+i][x+j] == '.':
                C[y+i][x+j] = count
                next_list.append((y+i,x+j))
    pre_list = next_list
print(count-1)


### FIXED CODE ###

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "#"
                tmp.append([nx, ny])
    state = tmp

print(ret-1)
### BUGGY CODE ###

import bisect
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = [0,0]
max = 0
i = n-1
if n == 2:
	ans[0] = a[1]
	ans[1] = a[0]
else:
	while i > (5*n//100):
		if a[i]%2 == 0:
			temp = n-1
			while a[i]//2 < a[temp]:
				temp += -1
			
			if a[i] > a[temp-1]:
				if (a[i]//2-a[temp-1]) <= (a[temp+1]-a[i]//2):
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp-1])*math.factorial(a[temp-1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp-1]
				else:
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp+1])*math.factorial(a[temp+1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp+1]
		else:
			temp1 = n-1
			temp2 = n-1
	
			while (a[i]+1)//2 < a[temp1]:
				temp1 += -1
			while (a[i]-1)//2 < a[temp2]:
				temp2 += -1
			
			if a[i] > a[temp1-1]:
				if (a[i]//2-a[temp1-1]) <= (a[temp1+1]-a[i]//2):
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp1-1])*math.factorial(a[temp1-1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp1-1]
				else:
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp1+1])*math.factorial(a[temp1+1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp1+1]
		
			if a[i] > a[temp2-1]:
				if (a[i]//2-a[temp2-1]) <= (a[temp2+1]-a[i]//2):
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp2-1])*math.factorial(a[temp2-1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp2-1]
				else:
					tmax = (math.factorial(a[i]))/(math.factorial(a[i]-a[temp2+1])*math.factorial(a[temp2+1]))
					if max < tmax:
						max = tmax
						ans[0] = a[i]
						ans[1] = a[temp2+1]
		i += -1
print(ans[0],ans[1])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mxm = max(a)
div = []
for i in range(n):
    div.append(abs(mxm/2.0-a[i]))
mini = min(div)
ind = div.index(mini)

if n == 2:
    print(max(a),min(a))
else:
    print(mxm,a[ind])
### BUGGY CODE ###

n= int(input())
ans=0
s=list(input())
#print(s)
    
for i in range(n):
	for j in range(i+1,n):
		if s[i]==s[j]:
			continue
		else:
			for k in range(j+1,n):
				if s[i]!=s[k] and s[j]!=s[k] and j-i!=k-j:
					ans+=1
print(ans)

### FIXED CODE ###

n= int(input())
ans=0
s=list(input())

G=s.count('G') 
R=s.count('R')
B=s.count('B')

ans= G*R*B

if n<=2:
	print(0)
else:
	for i in range(n-2):
		for j in range(min(i+1,n-2-i)):
			if s[i+1]!=s[i-j] and s[i+1]!=s[i+2+j] and s[i-j]!=s[i+2+j]:
				ans-=1
	print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    m = min(P[:i+1])
    if m >= P[i]:
        ans += 1 

print(ans)

### FIXED CODE ###

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

ans = 0
m = 10 ** 6
for i in range(N):
    if P[i] <= m:
        ans += 1
        m = P[i]

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

def main():
    from sys import stdin
    input = stdin.readline

    n, m, k = map(int, input().split())
    f = [[] for i in range(n)]
    BL = [[] for i in range(n)]
    ans = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        f[a-1].append(b-1)
        f[b-1].append(a-1)
    for _ in range(k):
        c, d = map(int, input().split())
        BL[c-1].append(d-1)
        BL[d-1].append(c-1)
    D = {}
    parent = [-1] * n
    visited = [False] * n
    for root in range(n):
        if visited[root]:
            continue
        D[root]  = set([root])
        stack = [root]
        while stack:
            x = stack.pop()
            visited[x] = True
            parent[x] = root
            for t in f[x]:
                if visited[t]:
                    continue
                D[root].add(t)
                stack.append(t)
    for i in range(n):
        grp = D[parent[i]]
        tans = len(grp) - len(f[i]) - 1
        for block in BL[i]:
            if block in grp:
                tans -= 1
        ans[i] = tans
    print(*ans)
main()

### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n, m, k = map(int, input().split())
    f = [[] for i in range(n)]
    BL = [[] for i in range(n)]
    ans = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        f[a-1].append(b-1)
        f[b-1].append(a-1)
    for _ in range(k):
        c, d = map(int, input().split())
        BL[c-1].append(d-1)
        BL[d-1].append(c-1)
    D = {}
    parent = [-1] * n
    visited = [False] * n
    for root in range(n):
        if visited[root]:
            continue
        D[root]  = set([root])
        stack = [root]
        while stack:
            x = stack.pop()
            visited[x] = True
            parent[x] = root
            for t in f[x]:
                if visited[t]:
                    continue
                D[root].add(t)
                stack.append(t)
    for i in range(n):
        grp = D[parent[i]]
        tans = len(grp) - len(f[i]) - 1
        for block in BL[i]:
            if block in grp:
                tans -= 1
        ans[i] = tans
    print(*ans)
main()
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    emir = input()
    if emir[0] == '1':
        s = s[::-1]
    elif emir[0] == '2':
        if emir[2] == '1':
            s = emir[4] + s
        elif emir[2] == '2':
            s += emir[4]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
string = []
is_normal = 1
saq = ""
sol = ""
for i in range(q):
    emir = input()
    if emir[0] == '1':
        is_normal *= -1
    elif emir[0] == '2':
        if is_normal == 1:
            if emir[2] == '1':
                sol += emir[4]
            elif emir[2] == '2':
                saq += emir[4]
        else:
            if emir[2] == '1':
                saq += emir[4]
            elif emir[2] == '2':
                sol += emir[4]
s = sol[::-1] + s + saq
if is_normal == -1:
    s = s[::-1]

print(s)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
  c = sum(a[i:i+k])
  d = sum(a[i+1:i+k+1])
  if c < d:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n - k):
  if a[i] < a[i + k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

ans = 0
while any(aa % 2 == 0 for aa in a):
  a.sort(reverse=True)
  odd = False
  for i in range(n):
    if a[i] % 2== 0 and odd == False:
      odd = True
      index = i
    if a[i] % 2 == 0 and i == index:
      a[i] /= 2
    elif a[i] % 2!= 0 or a[i] % 2 == 0 and odd ==False:
      a[i] *= 3
  ans += 1
print(ans)
    

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = sum((a & -a).bit_length() - 1 for a in A)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = [1]
while check:
    test = check.pop(0)
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()

### FIXED CODE ###

import sys, collections
input = sys.stdin.readline

n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = collections.deque([1])
while check:
    test = check.popleft()
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()
### BUGGY CODE ###

n = int(input())
l = []
for _ in range(n):
  l.append(int(input()))
m = max(l)
for i in range(0,n):
    if l[i] != m:
      print(m)
    else:
      l.pop(i)
      p = max(l)
      print(p)
      l.insert(i,m)

### FIXED CODE ###

import copy
n = int(input())
l = []
for _ in range(n):
  l.append(int(input()))
m = max(l)
k = copy.copy(l)
k.remove(m)
m2 = max(k)
for i in range(0,n):
    if l[i] != m:
      print(m)
    else:
      print(m2)
### BUGGY CODE ###

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

Q = int(input())
direction = 1
for i in range(Q):
    l = input().split()
    if l[0] == "1":
        direction *= -1
    else:
        if (l[1] == "1" and direction == 1) or (l[1] == "2" and direction == -1):
            S = l[2] + S
        else:
            S += l[2]

if direction == 1:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

Q = int(input())
query = [list(input().split()) for _ in range(Q)]
direction = 1
S_front = ""
S_back = ""
for l in query:
    if l[0] == "1":
        direction *= -1
    else:
        if (l[1] == "1" and direction == 1) or (l[1] == "2" and direction == -1):
            S_front += l[2]
        else:
            S_back += l[2]

if direction == 1:
    print(S_front[::-1] + S + S_back)
else:
    print(S_back[::-1] + S[::-1] + S_front)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()

for i in range(M):
    max_price = A_list.pop()
    bisect.insort(A_list, max_price // 2)

print(sum(A_list))

### FIXED CODE ###

# D 終了後再チャレンジ
# -*- coding: utf-8 -*-
import heapq

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list = [-a for a in A_list]
heapq.heapify(A_list)

for i in range(M):
    max_price = heapq.heappop(A_list) * (-1)
    heapq.heappush(A_list, max_price // 2 * (-1))
    
ans = sum(A_list) * (-1)
print(ans)
### BUGGY CODE ###

import itertools

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 10**19

for i in itertools.permutations(p,k):
    s = sum(i)
    if s < ans:
        ans = s

print(ans)

### FIXED CODE ###

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

q = sorted(p)

print(sum(q[:k]))
### BUGGY CODE ###

def solve(N, Q, S, L_R):
    answers = [None] * Q
    ac_index = list()
    for i in range(len(S) - 1):
        s = S[i:i + 2]
        if s == "AC":
            ac_index.append(i)
    q = 0
    for l, r in L_R:
        ans = 0
        for ac in ac_index:
            if l - 1 <= ac < r - 1:
                ans += 1
        answers[q] = ans
        q += 1
    return answers


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

### FIXED CODE ###

def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)