Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
a_list = [int(input()) for _ in range(M)]

mod = 1000000007
  
ans = 1
result = {0:1, 1:1}

def fib(x):
    if x == 0 or x == 1:
        return result[x]
    else:
        a = result.get(x-1) if result.get(x-1) else fib(x - 1)
        result[x-1] = a
        b = result.get(x-2)
        
        return a + b

x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a_list = [int(input()) for _ in range(M)]

mod = 1000000007

DP = [-1] * (N + 1) 
DP[0] = 1 
DP[1] = 1 

def fib(n):
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    
    return DP[n]

ans = 1
x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod
    
print(ans)
A, B, C = map(int, input().split())

combi = [A, B, C]
max_ABC = max([A, B, C])
other = [c for c in combi if c != max_ABC]
max_other = max(other)
min_other = min(other)

# Operation (1st method)
n_operation = max_ABC - max_other
max_other += n_operation
min_other += n_operation

# print(max_ABC, max_other, min_other, 'n_op:', n_operation)

# Operation (2nd method)
diff = max_ABC - min_other
if diff % 2 and diff == 1:
    n_add = (max_ABC - min_other) // 2 + 2
elif diff % 2:
    n_add = (max_ABC - min_other) // 2 + 1
else:
    n_add = (max_ABC - min_other) // 2
n_operation += n_add

print(n_operation)


### FIXED CODE ###

# WIP
A, B, C = map(int, input().split())

combi = [A, B, C]
set_abc = set(combi)

len_set_abc = len(set_abc)
max_set = max(set_abc)
min_set = min(set_abc)
if len_set_abc == 1:
    print(0)
elif len_set_abc == 2:
    max_freq = combi.count(max_set)
    diff = max_set - min_set
    if max_freq == 2 and diff % 2:
        print((diff + 1) // 2 + 1)
    elif max_freq == 2:
        print(diff // 2)
    else:
        print(diff)
else:
    other = [c for c in combi if c != max_set]
    max_other = max(other)
    min_other = min(other)
    
    n_operation = max_set - max_other
    max_other += n_operation
    min_other += n_operation

    diff = max_set - min_other
    if diff % 2 and diff == 1:
        n_add = (max_set - min_other) // 2 + 2
    elif diff % 2:
        n_add = (max_set - min_other) // 2 + 2
    else:
        n_add = (max_set - min_other) // 2
    n_operation += n_add

    print(n_operation)
N = int(input())

array = []

for i in range(N):
    array.append(list(map(int,input().split())))

test = []

t = []

for x in range(101):
    for y in range(101):
        H = []
        for i in array:
            if i[2] > 0:
                H_i = max(abs(i[0]-x)+abs(i[1]-y)+i[2],0)
                H.append(H_i)
        Hset = set(H)
        H = list(Hset)[0]
        if(len(Hset)==1 and H>=0):
            t.append([x,y,H])

if len(t) >=2:
    x = 15/0
            
print("{0[0]} {0[1]} {0[2]}".format(t[0]))


### FIXED CODE ###

N = int(input())

array = []

for i in range(N):
    array.append(list(map(int,input().split())))

test = []

t = []

for x in range(101):
    for y in range(101):
        H = []
        for i in array:
            if i[2] > 0:
                H_i = max(abs(i[0]-x)+abs(i[1]-y)+i[2],0)
                H.append(H_i)
        Hset = set(H)
        H = list(Hset)[0]
        if(len(Hset)==1 and H>=0):
            t.append([x,y,H])

if len(t) >= 2:
    t = []
    for x in range(101):
        for y in range(101):
            H = []
            for i in array:
                if True:
                    H_i = max(abs(i[0]-x)+abs(i[1]-y)+i[2],0)
                    H.append(H_i)
            Hset = set(H)
            H = list(Hset)[0]
            if(len(Hset)==1 and H>=0):
                t.append([x,y,H])
            
print("{0[0]} {0[1]} {0[2]}".format(t[0]))
n = int(input())
a = list(map(int,input().split()))
a.sort()
cnts = [0]*(a[-1]+1)
cnt2 = []
cnt4 = []
for i in range(len(a)):
    cnts[a[i]] += 1
    if cnts[a[i]] == 2:
        cnt2.append(a[i])
    if cnts[a[i]] == 4:
        cnt2.remove(a[i])
        cnt4.append(a[i])
ans = 0
if len(cnt2) <= 1 and not(cnt4):
    print(0)
else:
    if len(cnt2) >= 2:
        ans = max(ans, cnt2[-1]*cnt2[-2])
    if cnt4:
        ans = max(ans, cnt4[-1]**2)
    
    print(ans)



### FIXED CODE ###

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

adic = {}
for i in range(n):
    if a[i] not in adic:
        adic[a[i]] = 0
    adic[a[i]] += 1

alist = sorted(adic.items(),reverse = True)
before = 0
after = 0

for i in range(len(alist)):
    if before == 0:
        if alist[i][1] >= 4:
            before = alist[i][0]
            after = alist[i][0]
            break
        elif alist[i][1] >= 2:
            before = alist[i][0]
    else:
        if alist[i][1] >= 2:
            after = alist[i][0]
            break
print(before * after)
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

def max_calc(costs, st, remain=0):
    len_c = len(costs)
    max_c = -INF
    sum_c = 0
    for d in range(len_c + remain):
    # for d in range(len_c):
        i = (st + d) % len_c
        x = costs[i]
        sum_c += x
        max_c = max(max_c, sum_c)
    return max_c

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    cnt, remain = divmod(k, len(costs))
    len_c = len(costs)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = max_calc(costs, st)
            cost = max_c
            # print('1. cost',cost)

        else: # lp_c > 0:
            if cnt == 0:
                max_c = max_calc(costs, st)
                cost = max_c
                # print('2. cost',cost)

            else: # cnt > 0
                cost = lp_c * (cnt-1)
                max_c = max_calc(costs, st, remain)
                cost = max(cost, cost + max_c)

        score = max({score, cost})
print(score)



### FIXED CODE ###

n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 # lap count
    lap_sc = 0 # lap score
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break

        sum_sc += C[nx]
        score = sum_sc + max(0, lap_sc) * ((k - kc) // lc)
        max_score = max(max_score, score)

        nx = P[nx]
        if nx == st: break

print(max_score)

# print('===')
# print(n,k)
# print(P)
# print(C,end='\n\n')
S = ABC
if S = ABC:
 print("ARC")
else:
 print("ABC")

### FIXED CODE ###

s=input()
print("ABC" if s=="ARC" else "ARC")
A,B = map(int,input().split)
if A*B > A+B or A-B : print(A*B)
if A+B > A-B or A*B : print(A+B)
if A-B > A*B or A+B : print(A-B)

### FIXED CODE ###

A,B = map(int,input().split())
X = A + B
Y = A - B
Z = A * B
if X >= Y and X >= Z:
     print(X)
elif Y >= Z and Y >= X:
     print(Y)
elif Z >= X and Z >= Y:
     print(Z)
N = int(input())
A = [input() for _ in range(N)]
d = defaultdict(int)
for a in A:
    d[a] += 1

li = sorted(d.items())
l = sorted(li, key = itemgetter(0), reverse=True)
max_key = l[0][0]

for k, v in li:
    if k == max_key:
        print(k)
    else:
        continue

### FIXED CODE ###

def solve():
    import itertools
    from operator import itemgetter

    N = int(input())
    B = [input() for _ in range(N)]
    B.sort()

    l = []
    gr = itertools.groupby(B)
    max_key = 0
    for key, group in gr:
        length = len(list(group))
        l.append((length, key))
        if length > max_key:
            max_key = length

    l.sort(key = itemgetter(0), reverse=True)

    key = l[0][0]
    for k, v in l:
        if key == k:
            print(v)
        else:
            break

solve()
K,A,B=map(int,input().split())
n = (K-A-1) // (A-B) + 1
if A>=K: print(1)
elif A-B<=0: print(-1)
else: print(2*n +1)

### FIXED CODE ###

K,A,B=map(int,input().split())
if A>=K: print(1)
elif A-B<=0: print(-1)
else: 
  n = (K-A-1) // (A-B) + 1
  print(2*n +1)
a, b = map(double, input().split())
print(int(a * b))

### FIXED CODE ###

a, b = map(str, input().split())
a = int(a)
aux = int(b.replace(".", ""))
print((a * aux) // 100)
N = input()

if N % 2 == 0:
  print(int(N//2))
  
else:
  print(int(N//2+1))

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
  print(N//2)
  
else:
  print(N//2+1)
N = int(input())
L,R = map(int,input().split())

if L-R > 672:
    print(0)
else:
    minMod = 100000000
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if minMod > tmp:
                minMod = tmp
            elif tmp == 0:
                minMod = 0 
                break
    print(minMod)

### FIXED CODE ###

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

train = A*N
taxi  = B

if taxi < train:
    print(taxi)
else:
    print(train)
MOD = 10**9+7
N = int(input())
x = list(map(int,input().split()))

kaijo = 1
for i in range(1,N):
    kaijo *= i
    #kaijo %= MOD
"""for i in range(N-1):
    d[i] = x[i+1] - x[i]
    d[i] %= MOD
"""
prob = []
a = 0
for i in range(1,N):
    a += 1/i
    prob.append(a)
ans = 0
for i in range(1,N):

    """for j in range(1,i+1):
        prob += 1/j
    """
    ans += (x[i]-x[i-1]) * prob[i-1]
ans *= kaijo
ans %= MOD
ans = int(ans)
print(ans)

### FIXED CODE ###

MOD = 10**9+7
N = int(input())
x = list(map(int,input().split()))
x.sort()

kaijo = [1]
for i in range(1,N):
    kaijo.append(kaijo[-1]*i % MOD)

ans = 0
for i in range(N - 1):
    ans = (ans * (i+1) + (x[-1] - x[i]) * kaijo[i]) % MOD

print(ans)
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    if N%2==0:
        ans=0
        for i in range(0,N,2):
            ans+=A[i]
        ans=max(ans,sum(A)-ans)
        print(ans)
    else:
        """左から見ていく，i個を見たときに，
        iが偶数：
        　現在i//2個取得　or i//2 - 1取得(もう余裕がない)
        
        iが奇数：
        　現在i// +12個取得　or i//2取得(もう余裕がない)
        さらにi番目をとったか撮ってないかで2通り 
        ただし，余裕がある状態から取らないのは，数が足りなくなる
        """
        tight_get=[0]*N
        tight_not=[0]*N
        lo=[0]*N
        
        #最初だけ，取ったら必ずlooseになる
        lo[0]=A[0]
        lo[1]=A[1]
        
        for i in range(2,3):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i]+tight_not[i-1]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        for i in range(3,4):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        for i in range(4,N):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i],lo[i-4]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        print(max(tight_get[-1],tight_not[-1],lo[-1]))
    
    
    
        
        
        

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    """左から見ていく，i個を見たときに，
    i//2 ±1の範囲なので，状態は3N通り
    """
    
    p1=[-inf]*N
    zero=[-inf]*N
    n1=[-inf]*N
    
    p1[0]=A[0]
    zero[0]=0
    zero[1]=max(A[0],A[1])
    n1[1]=0
    
    for i in range(2,N):
        #偶奇で遷移の仕方に変化
        if i%2==0:
            p1[i]=max(p1[i-2]+A[i],p1[i-1])#2つ前の状態から取る or 1つ前の状態から取らない
            zero[i]=max(zero[i-2]+A[i],zero[i-1])
            n1[i]=max(n1[i-2]+A[i],n1[i-1])
        else:
            p1[i]=p1[i-2]+A[i]
            zero[i]=max(zero[i-2]+A[i],p1[i-1])
            n1[i]=max(n1[i-2]+A[i],zero[i-1])
            
    """        
    print(p1)
    print(zero)
    print(n1)"""
    
    print(zero[-1])
    
    
        
        
        

main()
A, B = list(map(int, input().split()))

for i in range(1, 2000):
    if floor(i * 0.08) == A and floor(i*0.1) == B:
        print(i)
        exit(0)
print(-1)


### FIXED CODE ###



from math import ceil, sqrt, floor

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

for i in range(1, 2000):
    if floor(i * 0.08) == A and floor(i*0.1) == B:
        print(i)
        exit(0)
print(-1)
a = int(input())
  import math
  print(2 * a * math.pi)

  

### FIXED CODE ###

import math
a = int(input())
print(2 * a * math.pi)
def croad():
    n,k = map(int,input().split())
	if n == 1:
	    print(0)
	else:
        x = list(map(int,input().split()))
        y = []
        for i in range(n-1):
                y.append(x[i+1]-x[i])
        y.sort()
        y.reverse()
        while k>1 and len(y)>0:
            y.pop(0)
            k -= 1
        print(sum(y))

a = int(input())
for i in range(a):
    croad()


### FIXED CODE ###

def croad():
    n,k = map(int,input().split())
    x = list(map(int,input().split()))
    y = []
    for i in range(n-1):
        y.append(x[i+1]-x[i])
    y.sort()
    y.reverse()
    while k>1 and len(y)>0:
        y.pop(0)
        k -= 1
    print(sum(y))

a = int(input())
for i in range(a):
    croad()
n = int(input())
 i = 0

 l = list(map(int, input().split()))
 Max = l[0]
 Min = l[0]
 for i in range(0,n):
 	
 	if l[i] > Max: l[i],Max = Max,l[i]
 	if l[i] < Min: l[i],Min = Min,l[i]
 	
 	sum = 0
 	sum += l[i]  
 	
print(f"{Min} {Max} {sum}")



### FIXED CODE ###

n = int(input())
i = 0

l = list(map(int, input().split()))
Max = l[0]
Min = l[0]
sum = 0
for i in range(0,n):
	sum += l[i]
	a = l[i]#変数の値が下の行の処理で変わってしまうのでaとかにしておく
	if a > Max:
		a,Max = Max,a
	if  a < Min:
		a,Min = Min,a
	
	
print(f"{Min} {Max} {sum}")
a = input().split()
if a[0] == a[1]:
    print(a[3])
elif a[0] == a[2]:
    print(a[1])
elif a[1] == a[2]:
    print(a[0])


### FIXED CODE ###

a = list(map(int, input().split()))
if a[0] == a[1]:
    print(a[2])
elif a[0] == a[2]:
    print(a[1])
elif a[1] == a[2]:
    print(a[0])
s = sorted(input())
t = sorted(input(),reverse=True)
ans = ""
def check_dict():
  for i in range(len(s)):
    if s[i] < t[i]:
      ans = "Yes"
      return ans
    elif s[i] > t[i]:
      ans = "No"
      return ans
  return ""
if len(s) < len(t):
  ans = check_dict()
  if ans == "":
    ans = "Yes"
  print(ans)
else:
  ans = check_dict()
  if ans == "":
    ans = "No"
  print(ans)

### FIXED CODE ###

s = sorted(input())
t = sorted(input(),reverse=True)
ans = ""
def check_dict():
  for i in range(min(len(s),len(t))):
    if s[i] < t[i]:
      ans = "Yes"
      return ans
    elif s[i] > t[i]:
      ans = "No"
      return ans
  return ""
if len(s) < len(t):
  ans = check_dict()
  if ans == "":
    ans = "Yes"
  print(ans)
else:
  ans = check_dict()
  if ans == "":
    ans = "No"
  print(ans)
from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=list(input().split())
    i=int(query[0])
    if i==1:
        direction=direction^1
    elif i==2:
        f,c=int(query[1]),query[2]
        if f==1 and direction==0:
            s.appendleft(c)
        elif f==1 and direction==1:
            s.append(c)
        elif f==2 and direction==0:
            s.append(c)
        elif f==2 and direction==1:
            s.appendleft(c)

if direction==0:
    print(''.join(s))
else:
    s=s[::-1]
    print(''.join(s))


### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=input()
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        i,f,c=query.split()
        if f=='1' and direction==0:
            s.appendleft(c)
        elif f=='1' and direction==1:
            s.append(c)
        elif f=='2' and direction==0:
            s.append(c)
        elif f=='2' and direction==1:
            s.appendleft(c)


if direction==0:
    print(''.join(s))
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(''.join(x))
[a,b,c]=list(map(int,input().split()))
if a<b<c
  print:{"true"}

### FIXED CODE ###

[a,b,c]=list(map(int,input().split()))
if a<=c<=b:
  print("Yes")
else:
  print("No")
S = (int.input())
print(S // 3600 ,":",S // 3600,":",S % 3600 )

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format(h,m,s))
import math

N, K = map(int, input().strip().split(' '))

ans = 0
count = int(math.log2(K)-math.log2(N))
if count < 0:
    count = 0
val = 2**count

for n in range(N, 0, -1):
    while n*val < K:
        val *= 2
        count *= 2
    #print('COUNT=', count)
    ans += 1.0/val

print(ans/N)


### FIXED CODE ###

import math
 
N, K = map(int, input().strip().split(' '))
 
ans = 0
count = int(math.log(K,2)-math.log(N,2))
if count < 0:
    count = 0
val = 2**count
 
for n in range(N, 0, -1):
    while n*val < K:
        val *= 2
        count *= 2
    #print('COUNT=', count)
    ans += 1.0/val
 
print(ans/N)
n=int(input())
x=list(map(int,list(input())))
def popcount(x):
  ret=0
  while x:
    if x%2==1:ret+=1
    x//=2
  return ret
def f(x):
  ret=0
  while x:
    x%=popcount(x)
    ret+=1
  return ret
from collections import Counter
xpop=Counter(x)[1]

xint_mi=sum([(pow(2,n-i-1,xpop-1)*y)%(xpop-1) for i,y in enumerate(x)])
xint_pl=sum([(pow(2,n-i-1,xpop+1)*y)%(xpop+1) for i,y in enumerate(x)])

for i,y in enumerate(x):
  if y:
    yint=xint_mi-pow(2,n-i-1)
    ypop=xpop-1
    yint%=ypop
  else:
    yint=xint_pl+pow(2,n-i-1)
    ypop=xpop+1
    yint%=ypop
  #print(yint,ypop)
  print(f(yint)+1)


### FIXED CODE ###

n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(0 if x=='1' else 1)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==0:
  for _ in range(n):
    print(1)
else:
  x0,x1=0,0
  for i in range(n):
    if x[i]=='1':
      if pcx!=1:
        x0+=pow(2,n-1-i,pcx-1)
        x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      if pcx==1:
        print(0)
      else:
        xx=x0-pow(2,n-1-i,pcx-1)
        xx%=pcx-1
        print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)
from itertools import combinations
N, D = map(int, input().split())
X = []
cnt = 0
for _ in range(N):
  X += list(map(int, input().split()))
print(combinations(N,2))


### FIXED CODE ###

from itertools import combinations
N, D = map(int, input().split())
X = []
for _ in range(N):
  X += list(map(int, input().split()))
cnt = 0
for i, j in combinations(range(N),2):
  d = 0
  for k in range(D):
    d += (X[i*D + k] - X[j*D + k])**2
  if int(d**0.5)**2 == d: cnt += 1
print(cnt)
import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2:
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+1)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+1)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n:
                DPy[i+1][j+y_d[i]] = True

if DPx[-2][x_n] and DPy[-2][y_n]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
gx -= x_d[0]
x_d[0] = 0
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2 or sum(x_d) < abs(gx) or sum(y_d) < abs(gy):
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True
if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")
N = int(input())
S = str(input())

if N % 2 == 0:
    T = str(S[:N/2])
    if S == T + T:
        print('Yes')
    else:
      print('No')
else:
    print('No')

### FIXED CODE ###

N = int(input())
S = str(input())

if N % 2 == 0:
    T = S[:int(N/2)]
    if S == T + T:
        print('Yes')
    else:
      print('No')
else:
    print('No')
import re


dd = input().strip().split(' ')
N, Q = tuple(map(int, dd))
S = input().strip()

ac_indicies = []
cp = S.find('AC')
while cp != -1:
    ac_indicies.append(cp)
    cp = S.find('AC', cp + 1)

min_i = 0
ac = ac_indicies + [N]
l_index = []
for i in range(N):
    if i > ac[min_i]:
        min_i += 1
    l_index.append(min_i)

max_i = len(ac_indicies)
ac2 = [0] + ac_indicies
r_index = []
for i in range(N-1, -1, -1):
    if i < ac[max_i]:
        max_i -= 1
    r_index.append(max_i)
   
total = len(ac_indicies)
for i in range(int(Q)):
    l, r = tuple(map(int, input().strip().split(' ')))
    print(total - l_index[l-1] - r_index[r-1])


### FIXED CODE ###

dd = input().strip().split(' ')
N, Q = tuple(map(int, dd))
S = input().strip()

ac_indicies = []
cp = S.find('AC')
while cp != -1:
    ac_indicies.append(cp)
    cp = S.find('AC', cp + 1)

min_i = 0
ac = ac_indicies + [N]
l_index = []
for i in range(N):
    if i > ac[min_i]:
        min_i += 1
    l_index.append(min_i)

total = len(ac_indicies)
for i in range(int(Q)):
    l, r = tuple(map(int, input().strip().split(' ')))
    print(l_index[r-1] - l_index[l-1])