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

s = str(input())
q = int(input())
b = 1
for i in range(q):
  la = input()
  if la == "1":
    b ^= 1
  else:
    a,f,c = la.split()
    if (int(f)-1)^b:s=c+s
    else:s=s+c
      
print(s if b==1 else s[::-1])

### FIXED CODE ###

s = str(input())
q = int(input())
b = 1
x=''
y=''
for i in range(q):
  la = input()
  if la == "1":
    b ^= 1
  else:
    a,f,c=la.split()
    if f == "1":
      if b==1:x=c+x
      else:y=y+c
    else:
      if b==1:y=y+c
      else:x=c+x
s = x+s+y      
print(s if b==1 else s[::-1])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
s = [0] * k
for i in range(k):
    s[i] = list(map(int, input().split()))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    for lr in s:
        for d in range(lr[0], lr[1]+1):
            if i+d <= n:
                dp[i+d] = (dp[i+d] + dp[i]) % mod

print(dp[n] % mod)


### FIXED CODE ###

# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])
### BUGGY CODE ###

#17:33
n,m = map(int,input().split())
mod = 10 ** 9 + 7
i = 2
tmp = 0
fact = []
while i <= m:
  if m % i == 0:
    m //= i
    tmp += 1
  else:
    if tmp > 0:
      fact.append(tmp)
    i += 1
    tmp = 0
if tmp > 0:
  fact.append(tmp)
#print(fact)
ans = 1
def inv(y):
  z = 1
  while y != 1:
    z *= mod // y + 1
    z %= mod
    y = y - mod % y
  return z
#print(inv(5))
for x in fact:
  for j in range(x):
    ans *= n+j
    ans %= mod
    ans *= inv(j+1)
    ans %= mod
print(ans)

### FIXED CODE ###

#17:33
n,m = map(int,input().split())
mod = 10 ** 9 + 7
i = 2
tmp = 0
fact = []
while i ** 2 <= m:
  if m % i == 0:
    m //= i
    tmp += 1
  else:
    if tmp > 0:
      fact.append(tmp)
    i += 1
    tmp = 0
if m == i:
  tmp += 1
  fact.append(tmp)
else:
  if tmp > 0:
    fact.append(tmp)
  if m > 1:
    fact.append(1)
#print(fact)
ans = 1
def inv(y):
  z = 1
  while y != 1:
    z *= mod // y + 1
    z %= mod
    y = y - mod % y
  return z
#print(inv(5))
for x in fact:
  for j in range(x):
    ans *= n+j
    ans %= mod
    ans *= inv(j+1)
    ans %= mod
print(ans)
### BUGGY CODE ###

S = list(input())
MOD = 10 ** 9 + 7

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])


### FIXED CODE ###

S = list(input())
MOD = 10 ** 9 + 7

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
e_p = []
for i in range(n):
    e_pi = (1 + p[i]) / 2
    e_p.append(e_pi)

maxp = 0
for i in range(n + 1 - k):
    e_temp = 0
    for j in range(k):
        e_temp += e_p[i + j]
    if e_temp > maxp:
        maxp = e_temp
print(maxp)

### FIXED CODE ###

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

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

ml = [0 for _ in range(n)]

while len(set(dl)) != 1 :
    for i in range(n) :
        if dl[i] == max(dl) :
            if dl[i-1] >= dl[(i+1)%n] :
                lain = dl[i]-dl[(i+1)%n]
                dl[i-1] -= lain
                dl[i] -= lain
                ml[i] += 2*lain
            else :
                lain = dl[i]-dl[i-1]
                dl[i] -= lain
                dl[(i+1)%n] -= lain
                ml[(i+1)%n] += 2*lain
else :
    for i in range(n) :
        ml[i] += dl[-1]

for i in range(n) :
    print(ml[i],end=" ")

### FIXED CODE ###

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

# m0 + m1 + m2 + m3 + m4 = d0 + d1 + d2 + d3 + d5
# d0 = (m0 + m1)//2
# d1 = (m1 + m2)//2
# d2 = (m2 + m3)//2
# d3 = (m3 + m4)//2
# d4 = (m4 + m0)//2
# m0 =  d0 - d1 + d2 - d3 + d4
# m1 =  d0 + d1 - d2 + d3 - d4
# m2 = -d0 + d1 + d2 - d3 + d4
# m3 =  d0 - d1 + d2 + d3 - d4
# m4 = -d0 + d1 - d2 + d3 + d4   
s = sum(a)
p = [0 for _ in range(n)]
q = [0 for _ in range(n+1)]
for i in range(n) :
    if i>1 :
        p[i] = p[i-2] + a[i-2]
    q[n-i-2] = q[n-i] + a[n-i-1]

print(*[s-2*p[i]-2*q[i] for i in range(n)])
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot
            
N,K,L=map(int,input().split())
ufroad = UnionFind(N)
uftrain = UnionFind(N)

for i in range(K):
    p,q = map(int,input().split())
    ufroad.unite(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    uftrain.unite(r-1,s-1)
uflist=[]
for i in range(N):
    uflist.append((ufroad.find(i), uftrain.find(i)))
counter={}
for i in range(N):
  if uflist[i] not in counter.keys():
    counter[uflist[i]]=1
  else:
    counter[uflist[i]]+=1
print(' '.join(map(str, [counter[uflist[i]] for i in range(N)])))

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot
            
N,K,L=map(int,input().split())
ufroad = UnionFind(N)
uftrain = UnionFind(N)

for i in range(K):
    p,q = map(int,input().split())
    ufroad.unite(p-1,q-1)
for i in range(L):
    r,s = map(int,input().split())
    uftrain.unite(r-1,s-1)
uflist=[]
for i in range(N):
    uflist.append((ufroad.find(i), uftrain.find(i)))
counter={}
for i in range(N):
  if uflist[i] not in counter.keys():
    counter[uflist[i]]=1
  else:
    counter[uflist[i]]+=1
print(' '.join(map(str, [counter[uflist[i]] for i in range(N)])))
### BUGGY CODE ###

# coding: utf-8
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cnts = Counter(A)
d = {}
for k in cnts.keys():
    if cnts[k] >= 2:
        d[k] = cnts[k] // 2
ans = 0
for i, k1 in enumerate(list(d.keys())[:-1]):
    for k2 in list(d.keys())[i:]:
        if k1 == k2:
            if d[k1] < 2:
                continue
            else:
                ans = max(ans, k1 * k2)
        else:
            ans = max(ans, k1 * k2)
print(ans)

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
Aset = list(set(A))
Aset.sort(reverse=True)
a, b = 0, 0
L = []
cnt = 1
for i in range(1, N):
    if A[i] == A[i-1]:
        cnt += 1
    else:
        L.append(cnt)
        cnt = 1
if A[-1] == A[-2]:
    L.append(cnt)
idx = 0
for i in range(len(L)):
    if L[i] >= 4:
        a, b = Aset[i], Aset[i]
        break
    elif L[i] >= 2:
        a = Aset[i]
        idx = i + 1
        break
if b <= 0:
    for i in range(idx, len(L)):
        if L[i] >= 2:
            b = Aset[i]
            break
print(a * b)
### BUGGY CODE ###

s = input()
ss = "".join(list(reversed(s)))
a = ["maerd","esare","resare","remaerd"]
flg = 0
while flg == 0:
	if ss[:5] ==a[0] or ss[:5] == a[1]:
		ss = ss[5:]
	elif ss[:6] == a[2]:
		ss = ss[6:]
	elif ss[:7] == a[3]:
		ss = ss[:7]
	else:
		flg = 1
	if len(ss) == 0:
		print ("YES")
		exit()
print ("NO")

### FIXED CODE ###

s = input()
a = ["eraser", "erase", "dreamer", "dream"]

for i in a:
	s = s.replace(i, "")
if s == "":
	print ("YES")
else:
	print ("NO")
### BUGGY CODE ###

import array

n= int(input())

maxN = 1000000
a = list(map(int, input().split()))

def calculate_prime():
    primes = [True] * maxN
    primes[0] = primes[1] = False
    prim = []
    prime_map = dict()
    for i in range(2, maxN):
        if primes[i] == True:
            prime_map[i] = 0
            prim.append(i)
            j = i * i
            while j < maxN:
                primes[j]= False
                j+=i
    return prime_map, array.array('i',prim)

prime_map, prim = calculate_prime()

#print(prim)
for i in list(set(a)):
    if i in prime_map:
        if prime_map[i] < 1:
            prime_map[i] = 1
    else:
        k = i
        for j in prim:
            if k % j == 0:
                tmp = 0
                while k % j == 0:
                    k = k // j
                    tmp += 1
                if tmp > prime_map[j]:
                    prime_map[j] = tmp
            if k in prime_map:
                if prime_map[k] < 1:
                    prime_map[k] = 1
                    break
            if k == 1:
                break

lcm = 1
for k, v in prime_map.items():
    if v > 0:
        lcm = lcm * (k**v)

#print(lcm)
result = 0

for i in a:
    result += lcm // i
    if result >= 1000000007:
        result = result % 1000000007

print(result)


### FIXED CODE ###

import array

n= int(input())

maxN = 1000000
a = list(map(int, input().split()))

def calculate_prime():
    primes = [True] * maxN
    primes[0] = primes[1] = False
    prim = []
    prime_map = dict()
    for i in range(2, maxN):
        if primes[i] == True:
            prime_map[i] = 0
            prim.append(i)
            j = i * i
            while j < maxN:
                primes[j]= False
                j+=i
    return prime_map, array.array('i',prim)

prime_map, prim = calculate_prime()

pppp = []
#print(prim)
for i in list(set(a)):
    if i in prime_map:
        if prime_map[i] < 1:
            pppp.append(i)
            prime_map[i] = 1

    else:
        k = i
        for j in prim:
            if k % j == 0:
                tmp = 0
                while k % j == 0:
                    k = k // j
                    tmp += 1
                if tmp > prime_map[j]:
                    if prime_map[j] == 0:
                        pppp.append(j)
                    prime_map[j] = tmp
            if k in prime_map:
                if prime_map[k] < 1:
                    pppp.append(k)
                    prime_map[k] = 1
                    break
            if k == 1:
                break

lcm = 1
for k in list(set(pppp)):
    lcm = lcm * (k**prime_map[k])

#print(lcm)
result = 0

for i in a:
    result += lcm // i

if result >= 1000000007:
    result = result % 1000000007
print(result)
### BUGGY CODE ###



tmp = input().split(" ")
n = tmp[0]
q = int(tmp[1])

s = input()

for i in range(q):
    tmp = input().split(" ")
    a = int(tmp[0]) - 1
    b = int(tmp[1])
    sub = s[a:b]
    start=0
    count=0
    while True:
        ind = sub.find("AC", start)
        if ind != -1:
            start=ind+2
            count += 1
        else:
            break
    print(count)


### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,q = get_nums_l()
s = input()

ruiseki_ac = [0] * (n+1)

for i in range(n-1):
    x = 0
    if s[i] == "A" and s[i+1] == "C":
        x = 1
    ruiseki_ac[i+1] = ruiseki_ac[i] + x
ruiseki_ac[n] = ruiseki_ac[n-1]

log(ruiseki_ac)

for i in range(q):

    a,b = get_nums_l()
    print(ruiseki_ac[b-1] - ruiseki_ac[a-1])
### BUGGY CODE ###

import itertools

n = int(input())
s = [int(x) for x in input()]

print(len(set(itertools.combinations(s, 3))))

### FIXED CODE ###

n = int(input())
s = list(map(int, input()))

ans = []

for i in range(10):
    if i in s:
        a = s.index(i)
        for j in range(10):
            if j in s[a + 1 :]:
                b = [x for x, y in enumerate(s) if x > a and y == j][0]
                for k in range(10):
                    if k in s[b + 1 :]:
                        ans.append(f"{i}{j}{k}")
print(len(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
INF = 10 ** 9
memo = [-1]*n
memo[0] = 0

def dp(i):
    if (memo[i] != -1):
        return memo[i]
    ans = INF
    for j in range (max(0, i-k),i):
        ans = min(ans, dp(j) + abs(h[i] - h[j]))
    memo[i] = ans
    return memo[i]

print(dp(n-1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
memo = [0]*n
for i in range(1, n):
    min_k = float('inf') 
    min_k=min([memo[j] +abs(h[i]-h[j]) for j in range(max(0, i-k), i)])
    memo[i] = min_k

print(memo[-1])
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
Z=[K for i in range(N)]
for i in A:
    for c in range(N):
        if c==i-1:
            continue
        else:
            Z[c]=Z[c]-1
for t in Z:
    if t<=0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N,K,Q=map(int,input().split())
l=[0 for i in range(N)]
for t in range(Q):
    A=int(input())
    l[A-1]+=1
for i in range(N):
    if K-(Q-l[i])<=0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

K,S = map(int,input().split())
cnt = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z ==S:
                cnt +=1

print(cnt)

### FIXED CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = sys.stdin.readline

K,S = map(int,input().split())
cnt = 0

for x in range(K+1):
    for y in range(K+1):
        z =S - x - y
        if z <=K and z>=0:
            cnt +=1

print(cnt)
### BUGGY CODE ###

from collections import defaultdict
s = input()
n = len(s)
dp = defaultdict(int)
dp[0] = 1
ls = [1<<(ord(s[0])-97)]
for i in range(1,n):
  ls.append(ls[-1]^(1<<(ord(s[i])-97)))
if ls[-1] == 0:
  print(1)
  exit()
for i in range(n):
  for b in range(26):
    bit = 1<<b
    if dp[ls[i]^bit] == 0:
      continue
    if dp[ls[i]] == 0:
      dp[ls[i]] = dp[ls[i]^bit]+1
    else:
      dp[ls[i]] = min(dp[ls[i]^bit]+1,dp[ls[i]])
print(dp[ls[n-1]]-1)

### FIXED CODE ###

from collections import defaultdict
s = input()
n = len(s)
dp = defaultdict(int)
dp[0] = 1
ls = [1<<(ord(s[0])-97)]
for i in range(1,n):
  ls.append(ls[-1]^(1<<(ord(s[i])-97)))
if ls[-1] == 0:
  print(1)
  exit()
for i in range(n):
  for b in range(26):
    bit = 1<<b
    if dp[ls[i]^bit] == 0:
      continue
    if dp[ls[i]] == 0:
      dp[ls[i]] = dp[ls[i]^bit]+1
    else:
      dp[ls[i]] = min(dp[ls[i]^bit]+1,dp[ls[i]])
print(dp[ls[n-1]]-1)
### BUGGY CODE ###

n = int(input())
keep = []
ans = 0
for i in range(n):
    j = int(input())
    if j in keep:
        keep.remove(j)
        ans -= 1
    else:
        keep.append(j)
        ans += 1
print(ans)


### FIXED CODE ###

import collections


n = int(input())
keep = []
ans = 0
for i in range(n):
    j = int(input())
    keep.append(j)

c = collections.Counter(keep)
print(len([i[0] for i in c.items() if i[1] % 2 != 0]))
### BUGGY CODE ###

N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
count = 0
for i in range(N):
    count += 1
    th_list.append(n)
#   print(n)
    n = city_list[n] - 1
''' if n in th_list:
        #繰り返されている個数を出す
        num = len(th_list)-th_list.index(n)
        break'''
 
#print(city_list, th_list)
count = -1
for i in range(N):
    if th_list.count(th_list[i]) > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]
#print(list)
#print(list[0])
#print(th_list)
if K > N:
    print(th_list[(K-list[0])%(list[1]-list[0])+list[0]]+1)
else:
    print(th_list[K]+1)

### FIXED CODE ###

import collections

N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
for i in range(N):
    th_list.append(n)
    n = city_list[n] - 1

c = collections.Counter(th_list)
for i in range(N):
    if c[th_list[i]] > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]

if K > N:
    print(th_list[(K - list[0]) % (list[1] - list[0]) + list[0]] + 1)
else:
    print(th_list[K] + 1)
### BUGGY CODE ###

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           is_visited[next_h][next_w] or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

# ABC122-C
import numpy as np
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
ind = []
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        ind.append(i+1)
##print(ind)
ind = np.array(ind)
##print(ind)
for i in range(Q):
    print(np.count_nonzero((lr[i][0] <= ind) & (ind <= lr[i][1] - 1)))

### FIXED CODE ###

# ABC122-C
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
cnt_list = [0] * N
tmp = 0
for i in range(N-1):
    cnt_list[i] = tmp
    if S[i] == "A" and S[i+1] == "C":
        tmp += 1
cnt_list[N-1] = tmp
##print(cnt_list)
for i in range(Q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    print(cnt_list[r] - cnt_list[l])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

n = int(input())
x = input()

def p(x):
    # x:str
    return x.count('1')

from functools import lru_cache

@lru_cache(maxsize=2 * 10 ** 6)
def f(n, k):
    b = bin(n) # binary str
    q = p(b[2:]) # 1の個数
    if q == 0:
        return k
    else:
        return f(n % q, k + 1)

nx = int(x, 2)
for i in range(n):
    if x[i] == '0':
        y = nx + pow(2, n - 1 - i)
    else:
        y = nx - pow(2, n - 1 - i) 
    print(f(y, 0))


### FIXED CODE ###

n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1 # 0になりうる
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

# f の前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i // 2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

# pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i - 1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i - 1] * 2 % zero_pop_count

for i in range(n-1, -1, -1):
    if x[n-i-1] == '1':
        if one_pop_count != 0:
            nxt = one_mod
        # nxt -= pow(2, i, one_pop_count)
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    elif x[n-i-1] == '0':
        nxt = zero_mod
        # nxt += pow(2, i, zero_pop_count)
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)
### BUGGY CODE ###

s = input()
total = 0

while '01' in s:
  total += s.count('01') * 2
  s = s.replace('01', '')

while '10' in s:
  total += s.count('10') * 2
  s = s.replace('10', '')

print(total)


### FIXED CODE ###

s = input()
total = 0

count_0 = s.count('0') * 2
count_1 = s.count('1') * 2

if count_0 < count_1:
  print(count_0)
else:
  print(count_1)