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

a = input()
c = input()
d=[]
alist = list(a)
for i in range(int(c)):
  e = input().split()
  d.append(e)
for i in range(int(c)):
  if d[i][0]=="1":
    l = len(alist)
    for x in range(int(l//2)):
      alist[x],alist[l-x-1] = alist[l-x-1],alist[x]
  else:
    if d[i][1] == "1":
      alist = [d[i][2]] + alist
    else:
      alist = alist + [d[i][2]]
le = len(alist)
answer =""
for i in range(le):
  answer = answer + alist[i]
print(answer)

### FIXED CODE ###

from collections import deque
a = input()
c = input()
d = []
alist = list(a)
adeque = deque(a)
count = 0
for i in range(int(c)):
  e = input().split()
  d.append(e)
for i in range(int(c)):
  if d[i][0]=="1":
    count = count + 1
  else:
    if d[i][1] == "1" and count % 2 == 0:
      adeque.appendleft(d[i][2])
    elif d[i][1] == "2" and count % 2 == 1:
      adeque.appendleft(d[i][2])
    else:
      adeque.append(d[i][2])
alist = list(adeque)
if count % 2 == 1:
  l = len(alist)
  for x in range(int(l//2)):
    alist[x],alist[l-x-1] = alist[l-x-1],alist[x]
answer = "".join(alist)
print(answer)
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

ans = []
for k in reversed(range(1, N + 1)):
    if k == 1:
        if len(ans) % 2 != a[k - 1]:
            ans.append(k)
        continue
    t = N // k
    cnt = 0
    for i in range(1, t + 1):
        if i * k in ans:
            cnt += 1
    if cnt % 2 != a[k - 1]:
        ans.append(k)

x = len(ans)
print(x)
if x >= 0:
    print(*ans)


### FIXED CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

ans = []
for k in reversed(range(1, N + 1)):
    if a[k - 1] == 1:
        ans.append(k)
        tmp = 1
        while tmp * tmp <= k:
            if k % tmp == 0:
                a[tmp - 1] ^= 1
                if tmp != k // tmp:
                    a[k // tmp - 1] ^= 1
            tmp += 1

x = len(ans)
print(x)
if x >= 0:
    print(*ans)
### BUGGY CODE ###

N = int(input())
from collections import defaultdict
d = dict()
d[0] = defaultdict(int)
d[1] = defaultdict(int)
for i in map(int,input().split()):
  for idx,j in enumerate(reversed('{:b}'.format(i))):
    d[int(j)][idx]+=1

m = max(set(d[0].keys()) | set(d[1].keys()) )

print(int(sum([((2**i)* (N-d[1][i])*d[1][i])%(1e9+7) for i in range(m+1)])%(1e9+7)))


### FIXED CODE ###

N = int(input())
from collections import defaultdict
d = defaultdict(int)
for i in map(int,input().split()):
  for idx,j in enumerate(reversed('{:b}'.format(i))):
    if j == "1":
      d[idx]+=1

m = max( set(d.keys())|set([0]))
print(int(sum([((2**i)* (N-d[i])*d[i])%(1e9+7) for i in range(m+1)])%(1e9+7)))
### BUGGY CODE ###

N = int(input())
A = [0 * x for x in range(N)]
B = [0 * x for x in range(N-1)]

for i in range(N):
  A[i] = int(input())

for i in range(N):
  print(max(A[:i]+A[i+1:]))

### FIXED CODE ###

N = int(input())
A = [0 * x for x in range(N)]
B = [0 * x for x in range(N-1)]

for i in range(N):
  A[i] = int(input())

flag = False
M = max(A)
if A.count(M) > 1:
  flag = True
for i in range(N):
  if A[i] == M:
    if flag:
      print (M)
    else:
      print(max(A[:i]+A[i+1:]))
  else:
    print (M)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
H = [INT() for i in range(N)]
H.sort()
ans = INF
for i in range(N-K+1):
    mi = H[i:i+K][0]
    ma = H[i:i+K][-1]
    tmp = ma - mi
    ans = min(tmp, ans)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
#for i in range(n-k+1):
print(min(h[i+k-1]-h[i] for i in range(n-k+1)))
### BUGGY CODE ###

#! /usr/bin/env python3

def dropcell():
    for y in range(H):
        for i in range(H):
            for j in range(W):
                if gm[H-i][j] == 0:
                    gm[H-i-1][j], gm[H-i][j] = gm[H-i][j], gm[H-i-1][j]
def removecell():
    global gp, gf
    gf = False
    p = 0
    for y in range(H):
        c = 1
        t = 0
        for i in range(W+1):
            x = gm[y+1][i]
            if x > 0 and x == t:
                c += 1
            else:
                if c >= K:
                    for j in range(c):
                        gm[y+1][i-1-j] = 0
                    p += (t * c)
                    gf = True
                t = x
                c = 1
    gp += p * (2**gi)


H, W, K = map(int, input().split())
M = [[0]*(W+1)]+[list(map(int, list(input())))+[0] for i in range(H)]
points = {}
for i in range(H)[::-1]:
    for j in range(W):
        gp = 0
        gf = True
        gi = 0
        gm = [[j for j in i]for i in M]
        gm[i+1][j] = 0
        while gf:
            dropcell()
            removecell()
            gi += 1
        points[gp] = 1
print(max(points))

### FIXED CODE ###

#! /usr/bin/env python3

def dropcell(h, w, rm):
    for i in range(w):
        y = 0
        for j in range(h):
            if rm[h-j-1][i] != 0:
                rm[h-y-1][i] = rm[h-j-1][i]
                y += 1
        for j in range(h-y):
            rm[h-y-j-1][i] = 0

def removecell(h, w, k, rm, a):
    p = 0
    for y in range(h):
        c, t = 1, 0
        for i in range(w+1):
            x = rm[y][i]
            if x > 0 and x == t:
                c += 1
            else:
                if c >= k:
                    for j in range(c):
                        rm[y][i-1-j] = 0
                    p += (t * c)
                t = x
                c = 1
    return p * (2**a)

def game(h, w, k, M, y, x):
    f, score, a = 1, 0, 0
    rm = [[j for j in i]for i in M[:y+1]]
    rm[y][x] = 0
    while f:
        dropcell(len(rm), w, rm)
        f = removecell(len(rm), w, k, rm, a)
        score += f
        a += 1
    return score

def main():
    H, W, K = map(int, input().split())
    M = [list(map(int, list(input())))+[0] for i in range(H)]
    ans = 0
    for j in range(W):
        t = 0
        for i in range(1, H):
            if M[i][j] != t:
                ans = max(ans, game(H, W, K, M, i, j))
                t = M[i][j]
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
import collections
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [(int(s[len(s) - i - 1]) * (10 ** i)) % 2019 for i in range(len(s))]
	nums = [0] + [x % 2019 for x in np.cumsum(nums)]
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])

s = input()
print(main(s))

### FIXED CODE ###

import collections
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	p = 0.1
	for i in range(len(s)):
		p = int(p * 10) % 2019
		cur = (cur + int(s[len(s) - 1 - i]) * p) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))
### BUGGY CODE ###

from collections import deque


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

INF = 10 ** 5
d = [[10 ** 5] * W for _ in range(H)]

q = deque()

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            d[i][j] = 0
            q.append((i, j))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

ans = 0
while q:
    y, x = q.popleft()

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            A[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))
            ans = max(ans, d[ny][nx])

print(ans)

### FIXED CODE ###

from collections import deque


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

INF = 10 ** 5
d = [[10 ** 5] * W for _ in range(H)]

q = deque()

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            d[i][j] = 0
            q.append((i, j))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

while q:
    y, x = q.popleft()

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            A[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, d[i][j])

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

N,K=map(int, input().split())
A=list(map(int, input().split()))
import numpy as np

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  A=np.cumsum(D)
  return A 

for i in range(K):
  D=f(A)
  A=list(D)  
  if A[:-1]==[N]*(N):
    break
print(*A[:-1])

### FIXED CODE ###

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import numpy as np
import scipy

#N = int(input())
#C = [[0 for i in range(3)] for j in range(3)]
#for i in range(3):
#    C[i] = list(map(int, input().split()))
S = list(map(int, input().split()))
#A, B, C = map(int, input().split())

def plus1(X, Y):
    return X+1, Y+1

def plus2(Z):
    return Z+2

c = 0
S = sorted(S)

while True:
    S[0], S[1] = plus1(S[0], S[1])
    c += 1
    if S[1] == S[2]:
        break

if (S[1] - S[0])%2 != 0:
    S[1], S[2] = plus1(S[1], S[2])
    c += 1

while True:
    S[0] = plus2(S[0])
    c += 1
    if S[0] == S[1]:
        break

print(c)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import numpy as np
import scipy

#N = int(input())
#C = [[0 for i in range(3)] for j in range(3)]
#for i in range(3):
#    C[i] = list(map(int, input().split()))
S = list(map(int, input().split()))
#A, B, C = map(int, input().split())

def plus1(X, Y):
    return X+1, Y+1

def plus2(Z):
    return Z+2

c = 0
S = sorted(S)

while True:
    if S[1] == S[2]:
        break
    S[0], S[1] = plus1(S[0], S[1])
    c += 1

if (S[1] - S[0])%2 != 0:
    S[1], S[2] = plus1(S[1], S[2])
    c += 1

while True:
    if S[0] == S[1]:
        break
    S[0] = plus2(S[0])
    c += 1

print(c)
### BUGGY CODE ###

N = int(input())

S = []
cnt = 0

for i in range(N):
    s = "".join(sorted(list(input())))
    cnt += S.count(s)
    S.append(s)

print(cnt)

### FIXED CODE ###

N = int(input())

S = []
cnt = 0
c = {}

for i in range(N):
    s = "".join(sorted(list(input())))
    if s not in c.keys():
        c[s] = 1
    else:
        c[s] += 1
        cnt += c[s]-1
        
    S.append(s)

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

import sys
readline = sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
	a.append(list(map(int,input().split())))

play = [0 for _ in range(n)]
flag = [True for _ in range(n)]
count = 0
ans = 0
while True:
	break_flag = True
	for i in range(n):
		if flag[i]:
			num = a[i][play[i]]-1
			if flag[num] and a[num][play[num]]-1 == i:
				play[num] += 1
				play[i] += 1
				flag[num] = False
				flag[i] = False
				break_flag = False
				count += 1
	if break_flag:
		print(-1)
		sys.exit()
		break
	ans += 1
	if count == n*(n-1)//2:
		break
	for i in range(n):
		if play[i] < n-1:
			flag[i] = True
		else:
			flag[i] = False

if ans == 0:
	print(-1)
else:
	print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(n*(n-1)//2)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()
### BUGGY CODE ###


n=int(input())
a=[int(i) for i in input().split()]
a.sort()
i=1
while True:
    if len(a)<=1:
        break
    else:
        if i>=len(a):
            i=1
        if a[i] % a[0]==0:
            del a[i]
        else:
            a[i]-=a[0]
            if a[i]<=0:
                del a[i]
    a.sort()
    i+=1
print(a[0])

### FIXED CODE ###


n=int(input())
a=[int(i) for i in input().split()]
c=a[0]
def gcd(x,y):
    while y:
        x,y=y,x%y
    return x

for i in a:
    c=gcd(c,i)
print(c)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import sys
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def solve(N, A):
    mod = 10 ** 9 + 7
    lcm = lcm_list(A)
    ans = [lcm//a for a in A]
    return sum(ans) % mod


def main():
    read = sys.stdin.buffer.read
    
    N,*A = map(int,read().split())
    ans = solve(N, A)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
def solve(N, A):
    mod = 10 ** 9 + 7
    lcm = lcm_list(A)
    ans = [lcm//a for a in A]
    return sum(ans) % mod
    
 
def main():
    read = sys.stdin.buffer.read
    N,*A = map(int,read().split())
    ans = solve(N, A)
    print(ans)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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



Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
    
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)

maxval=len(Asum)-1

tmp=0
cnt=0
for i in range(len(Asum)):
  for j in range(len(Bsum)):
    cnt+=1
    j=tmp+j
    if j>=len(Bsum)-1:j=len(Bsum)-1
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==len(Bsum)-1:
      maxval=max(maxval,len(Asum)-1-i+j)
      break
print(maxval)


### FIXED CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  if lenA-1-i+lenB<maxval:break
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)
### BUGGY CODE ###

import numpy as np
import math
N,a,b = np.array(input().split()).astype(int)
def cmb(N, r, mod):
  return (math.factorial(N)%mod)//((math.factorial(r)%mod)*(math.factorial(N-r)%mod))
print(2**N-1-cmb(N, a, 10**9+7)-cmb(N, b, 10**9+7))

### FIXED CODE ###

import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = (x*x)%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n+1):
        val = val*i % mod
    return val
    
def cmb1(N, r):
    A = fact(N-r+1, N)%mod
    B = fact(1, r)%mod
    return A, B, (A*power(B, mod-2))%mod
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A%mod
    B = fact(b+1, a)*B%mod
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)
### BUGGY CODE ###

n = input().split()
N = int(n[0])
Q = int(n[1])
S = input()

ans = []
for i in range(Q):
    lr = input().split()
    l = int(lr[0])
    r = int(lr[1])
    tmp = S[l-1:r]
    count = tmp.count('AC')
    print(str(count))



### FIXED CODE ###

from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

tmp = []
for i in range(N-1):
    tmp_S  = S[i:i+2]
    if tmp_S == 'AC':
        tmp.append(1)
    else:
        tmp.append(0)

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))
#print(tmp2)

for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = 0
for q in qs:
    q = q.split()
    if q[0] == '1':
        rev += 1
        rev %= 2
    else:
        if (q[1]=='1' and rev==0) or (q[1]=='2' and rev==1):
            S = q[2] + S
        else:
            S += q[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

from itertools import combinations

n,m = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(m)]
class Unionfind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n
        
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return 
                
        if self.parents[x] > self.parents[y]:
            x ,y = y,x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
 
ans = [n*(n-1)//2]
island = Unionfind(n)
for a,b in reversed(AB[1:]):
    island.union(a-1,b-1)
    num = [island.size(r) for r in island.roots()]
    cnt = 0
    for v,w in combinations(num,2):
      cnt += v*w
    ans.append(cnt)
        
for a in reversed(ans):
    print(a)
    
    
    

### FIXED CODE ###

n,m = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(m)]
class Unionfind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n
        
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return 
                
        if self.parents[x] > self.parents[y]:
            x ,y = y,x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def size(self,x):
        return -self.parents[self.find(x)]
      
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
ans = [n*(n-1)//2]
island = Unionfind(n)
for a,b in reversed(AB[1:]):
  if island.same(a-1,b-1):
    cnt = ans[-1]
  else:
    cnt = ans[-1]-island.size(a-1)*island.size(b-1)
    island.union(a-1,b-1)
  ans.append(cnt)
        
for a in reversed(ans):
    print(a)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, q = map(int, readline().split())
    s = readline().rstrip().decode()
    
    for _ in range(q):
        l, r = map(int, readline().split())
        print(s[l-1:r].count('AC'))
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, q = map(int, readline().split())
    s = readline().rstrip().decode()
    ac = [0]    
    cnt = 0
    for i in range(1, n):
        if (s[i-1] == 'A') and (s[i] == 'C'):
            cnt += 1
            ac.append(cnt)
        else:
            ac.append(cnt)
    query = []
    for _ in range(q):
        l, r = map(int, readline().split())
        l -= 1
        r -= 1
        print(ac[r]-ac[l])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    SP = [input().split() for i in range(M)]
    wa_num = 0
    wa_num_temp = {}
    ac_num = 0
    ansed = []
    for sp in SP:
        if sp[0] in ansed:
            continue
        if sp[0] not in wa_num_temp:
            wa_num_temp[sp[0]] = 0
        if sp[1] == "WA" and sp[0] not in ansed:
            wa_num_temp[sp[0]] += 1
        elif sp[1] == "AC" and sp[0] not in ansed:
            ac_num += 1
            wa_num += wa_num_temp[sp[0]]
            ansed.append(sp[0])

    print(ac_num, wa_num)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    N, M = map(int, input().split())
    SP = [list(input().split()) for i in range(M)]
    was = [0] * N
    acs = [0] * N
    penaltyCount = 0
    for sp in SP:
        if acs[int(sp[0])-1] == 1:
            continue
        if acs[int(sp[0])-1] == 0 and sp[1] == "WA":
            was[int(sp[0])-1] += 1
        elif acs[int(sp[0])-1] == 0 and sp[1] == "AC":
            acs[int(sp[0])-1] = 1
            penaltyCount += was[int(sp[0])-1]

    print(sum(acs), penaltyCount)


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

n = int(input())
s = input()

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]
dp[0][0] = 1

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]
dp[0][0] = 1

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

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

N = int(input())
A = list(map(int, input().split()))
M = N//2
if N % 2 == 1 and A.count(0) == 1 and all(A.count(i*2)==2 for i in range(1,M-1)):
    print((2 ** M) % (10**9+7))
elif N % 2 == 0 and all(A.count(i*2-1)==2 for i in range(1, M-1)):
    print((2 ** M) % (10**9+7))
else:
    print(0)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
M = N//2
c = Counter(A)
if N % 2 == 1 and A.count(0) == 1 and all(c[i*2+2] == 2 for i in range(M)):
    print((2 ** M) % (10**9+7))
elif N % 2 == 0 and all(c[i*2+1]==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
else:
    print(0)