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

N,M = map(int,input().split())
A = []
MOD = 1000000007
for _ in range(M):
  a = int(input())
  A.append(a)
DP = [0]*(N+1)
DP[0] = 1
DP[1] = 1
if 1 in A:
  DP[1] = 0
for i in range(1,N):
  DP[i+1] = DP[i-1]+DP[i]
  if i+1 in A:
    DP[i+1] = 0
print(DP[-1]%MOD)

### FIXED CODE ###

N,M = map(int,input().split())
A = []
MOD = 1000000007
for _ in range(M):
  a = int(input())
  A.append(a)
DP = [1]*(N+1)
for i in A:
  DP[i] = 0
for i in range(2,N+1):
  DP[i] = (DP[i-1]+DP[i-2])%MOD*DP[i]
print(DP[-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
dis=[A[0]]
num=0
for i in range(1,len(A)):
    ind=0
    num+=dis.pop(ind)
    #L.insert(ind+1,A[i])
   
    dis.append(A[i])
    dis.append(A[i])
print(num)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
dis=deque([A[0]])
num=0
for i in range(1,len(A)):
    num+=dis.popleft()
    #L.insert(ind+1,A[i])
    dis.append(A[i])
    dis.append(A[i])
print(num)
#print(L)
#print(dis)
### BUGGY CODE ###

n = int(input())

R = []

for i in range(0,n):
    R.insert(i,int(input()))

MAX = R[1] - R[0]
for r in range(2,n):
    o = R[r] - min(R[:r])
    if(MAX < o):
        MAX = o
print(MAX)

### FIXED CODE ###

n = int(input())

R = []

for i in range(0,n):
    R.insert(i, int(input()))

maxV = -2000000000  # ????°??????????????????????????¨????????????????
minV = R[0]

for r in range(1, n):
    maxV = max(maxV, R[r] - minV)
    minV = min(minV, R[r])

print(maxV)
### BUGGY CODE ###

n = input()
s = input()

n = int(n)

ans = []

for i in range(n - 2):
    for j in range(i+1, n - 1):
        for k in range(j+1, n):
            ans.append(s[i]+s[j]+s[k])
            # print(s[i]+s[j]+s[k])

ans = list(set(ans))
print(len(ans))

### FIXED CODE ###

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

ans_count =0

for i in range(10):
    for j in range(10):
        for k in range(10):
            i_pos = s.find(str(i))

            if i_pos < 0:
                continue

            j_pos = s.find(str(j),i_pos+1)

            if j_pos < 0:
                continue

            k_pos = s.find(str(k), j_pos +1)

            if k_pos < 0:
                continue

            ans_count += 1

print(ans_count)
### BUGGY CODE ###

import bisect
n = int(input())
S = tuple(map(int, input().split()))
q = int(input())
T = tuple(map(int, input().split()))
cnt = 0
for n in T:
    cnt += n in S
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
S = tuple(map(int, input().split()))
q = int(input())
T = tuple(map(int, input().split()))
cnt = 0
for n in T:
    m = bisect.bisect_right(S, n)
    if m > 0 and S[m-1] == n:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    for i in range(n):
      count_temp = 0
      if not a[i] in a[:i] and not a[i] in a[i+1:]:
        for k in range(n):
          if i != k and a[i] % a[k] == 0:
            count_temp += 1
            break
        if count_temp == 0:
          count += 1
    print(count)
  
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
a=sorted(list(map(int,input().split())))
 
c=[1 for i in range(10**6+1)]
d = Counter(a)
s = list(set(a))
count = 0
if d[1] == 1:
  print(1)
  sys.exit()
elif d[1] >=2:
  print(0)
  sys.exit()
for x in s:
  t = x * 2
  while t <= 10 ** 6:
    c[t] = 0
    t += x
 
for x in a:
  if d[x] == 1 and c[x] == 1:
    count += 1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


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


H, W, M = MI()

R = np.zeros(H + 1)
C = np.zeros(W + 1)
bombs = []
for _ in range(M):
    h, w = MI()
    bombs.append((h, w))
    R[h] += 1
    C[w] += 1

R_max = np.where(R == max(R))
C_max = np.where(C == max(C))

ans = max(R) + max(C)
for r in R_max[0]:
    for c in C_max[0]:
        if (r, c) not in bombs:
            print(int(ans))
            exit()

print(int(ans - 1))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


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


H, W, M = MI()

R = np.zeros(H + 1)
C = np.zeros(W + 1)
bombs = []
for _ in range(M):
    h, w = MI()
    bombs.append((h, w))
    R[h] += 1
    C[w] += 1

R_max = [R == max(R)]
ans = max(R) + max(C)
C_max = [C == max(C)]

cnt = 0
for h, w in bombs:
    if R_max[0][h] and C_max[0][w]:
        cnt += 1

if cnt == np.count_nonzero(R_max) * np.count_nonzero(C_max):
    print(int(ans - 1))
else:
    print(int(ans))
### BUGGY CODE ###


def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

for i in m:
    if canProd(0,i,a,n):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

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

for i in range(1,ans):
    if P[i] > min(P[:i]): 
      ans -= 1 
  
print(ans + 1)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 1
small = P[0]
for i in range(1,N):
  if P[i] <= small: 
    ans += 1
    small = P[i]
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w = map(int, input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[]
for i in range(h):
    lis=[]
    for j in range(w):
        lis.append(abs(a[i][j]-b[i][j]))
    d.append(lis)

dp = [[[0 for _ in range(80*(h+w))] for _ in range(w)] for _ in range(h)]
dp = [[0 for _ in range(6400)] for _ in range(h*w)]
dp[0][d[0][0]]=1

for i in range(h*w):
    nowh,noww = divmod(i,w)
    for k in range(6400):
        if not dp[nowh*w + noww][k]==1:
            continue
        nxth,nxtw=nowh+1, noww+1
        if nxtw<w:
            nxt=d[nowh][nxtw]
            if k+nxt < 6400:
                dp[nowh*w + nxtw][k+nxt] = 1
            dp[nowh*w + nxtw][abs(k-nxt)] = 1
        if nxth<h:
            nxt=d[nxth][noww]
            if k+nxt < 6400:
                dp[nxth*w + noww][k+nxt] = 1
            dp[nxth*w + noww][abs(k-nxt)] = 1


for k in range(6400):
    if dp[-1][k]==1:
        print(k)
        exit()

### FIXED CODE ###

h,w = map(int, input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])

dp = [[0 for _ in range(6400)] for _ in range(h*w)]
dp[0][d[0][0]]=1

for i in range(h*w):
    nowh,noww = divmod(i,w)
    for k in range(6400):
        if not dp[nowh*w + noww][k]==1:
            continue
        nxth,nxtw=nowh+1, noww+1
        if nxtw<w:
            if k+d[nowh][nxtw] < 6400:
                dp[nowh*w + nxtw][k+d[nowh][nxtw]] = 1
            dp[nowh*w + nxtw][abs(k-d[nowh][nxtw])] = 1
        if nxth<h:
            if k+ d[nxth][noww]< 6400:
                dp[nxth*w + noww][k+d[nxth][noww]] = 1
            dp[nxth*w + noww][abs(k-d[nxth][noww])] = 1


for k in range(6400):
    if dp[-1][k]==1:
        print(k)
        exit()
### BUGGY CODE ###

def solve():
    N = int(input())
    Ass = []
    for _ in range(N):
        As = list(map(lambda x: int(x)-1, input().split()))
        Ass.append(As+[N])

    iAs = [0] * N
    ans = 1
    while True:
        useds = [False] * N
        isOK = False
        for i in range(N):
            if useds[i]: continue
            j = Ass[i][iAs[i]]
            if j == N or useds[j]: continue
            if Ass[j][iAs[j]] == i:
                iAs[i] += 1
                iAs[j] += 1
                useds[i] = True
                useds[j] = True
                isOK = True
        if not isOK:
            print(-1)
            return
        if sum(iAs) == N*(N-1):
            print(ans)
            return
        ans += 1

solve()


### FIXED CODE ###

def solve():
    N = int(input())
    Ass = []
    for _ in range(N):
        As = list(map(lambda x: int(x)-1, input().split()))
        Ass.append(As+[N])

    games = []
    numReadyss = [[0]*(N) for _ in range(N)]
    iAs = [0] * N
    for i in range(N):
        j = Ass[i][iAs[i]]
        if j > i: i, j = j, i
        numReadyss[i][j] += 1
        if numReadyss[i][j] >= 2:
            games.append((i, j))
    ans = 1
    numOK = 0
    while True:
        if not games:
            print(-1)
            return
        game2s = []
        for i, j in games:
            iAs[i] += 1
            i2 = Ass[i][iAs[i]]
            if i2 == N:
                numOK += 1
            else:
                if i2 > i: i, i2 = i2, i
                numReadyss[i][i2] += 1
                if numReadyss[i][i2] >= 2:
                    game2s.append((i, i2))
            iAs[j] += 1
            j2 = Ass[j][iAs[j]]
            if j2 == N:
                numOK += 1
            else:
                if j2 > j: j, j2 = j2, j
                numReadyss[j][j2] += 1
                if numReadyss[j][j2] >= 2:
                    game2s.append((j, j2))
        if numOK >= N:
            print(ans)
            return
        ans += 1
        games = game2s


solve()
### BUGGY CODE ###

l=input()
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)

def func(li):
  if '0' not in li:
    return pow(3,len(li),mod)
  elif len(li)==1:
    if li=='1':
      return 3
    else:
      return 1
  elif li[0]=='0':
    return func(li[1:])%mod
  else:
    ret=(2*func(li[1:]))%mod
    ret+=func('1'*(len(li)-1))%mod
    return ret%mod
print(func(l))


### FIXED CODE ###

l=input()
n=len(l)
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)
#dp1,dp2=[0]*n,[0]*n
dp1,dp2=0,1
for i in range(n):
  if l[i]=='0':
    dp1*=3
  else:
    dp1*=3
    dp1+=dp2
    dp2*=2
  dp1%=mod
  dp2%=mod
print((dp1+dp2)%mod)
### BUGGY CODE ###

def main():
  import sys
  from numpy import zeros
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=zeros((n*2,26),int)
  def update(i,x):
    i+=n
    data[i]=zeros(26,int)
    data[i,x]=1
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=zeros(26,int)
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return s.sum()
  for i,c in enumerate(input()[:-1],n):data[i,c-97]=1
  for i in range(n-1,0,-1):data[i]=data[i*2]|data[i-~i]
  s=[]
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:s+=query(int(a)-1,int(b)),
    else:update(int(a)-1,b[0]-97)
  print('\n'.join(map(str,s)))
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
### BUGGY CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
# A.sort(reverse=True)
# keta = (len(bin(K)[2:]))
# num1s = [0] * keta
# for a in A:
#     for j in range(keta):
#         if (1 << j) & a :
#             num1s[j] = num1s[j] + 1
# #print(num1s)
# #print("keta")
# #print(keta)

# half = float(N)/2
# X = 0
# if K != 0:
#     for j in range(0,keta):
#         #print("j:")
#         #print(j)
#         if num1s[j] < half:
#             X = X + (1<<j)
# answer = 0
# #print(A)
# for a in A:
#     #print(a^X)
#     answer = (a ^ X) + answer
# print(answer)


def f(A,X):
    r = 0
    for a in A:
        r = r + (a^X)
    return r

answer = 0
for k in range(K+1):
    tmp = f(A,k)
    if answer < tmp:
        answer = tmp
print(answer)



### FIXED CODE ###

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

# if K ==0:
#     keta = 0
# else:
#     keta = (len(bin(K)[2:]))
keta = (len(bin(K)[2:]))

num1s = [0] * keta
for a in A:
    for j in range(keta):
        if (1 << j) & a :
            num1s[j] = num1s[j] + 1
#print(num1s)
#print("keta")
#print(keta)

half = N/2
X = 0
if K != 0:
    for j in range(keta):
        #print("j:")
        #print(j)
        #if num1s[j] < half:
            X = X + ((num1s[j] < half)<<j)
answer = 0
#print(X)


def f (X):
    r = 0
    for a in A:
        r = r + (a^X)
    return r

maxfx = f(K)
for j in range(keta):
    if (1<<j)&K:
        
        x = (((1<<j) -1)&X ) 
        x = x | ((~((1<<(j+1))-1))&K)
        if f(x) > maxfx:
            maxfx = f(x)
            #print(x,maxfx,f(x)) 
print(maxfx)
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += math.gcd(math.gcd(i+1,j+1),k+1)
print(ans)


### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(gcd(i,j),k)
print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(sorted([int(a) for a in input().split()], reverse=True))
B = tuple(sorted([int(b) for b in input().split()], reverse=True))
C = tuple(sorted([int(c) for c in input().split()], reverse=True))
ans = 0

for i in range(N):
  for j in range(N):
    if A[i] >= B[j]:
      break
    for k in range(N):
      if B[j] >= C[k]:
        break
      else:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()])
B = [int(b) for b in input().split()]
C = sorted([int(c) for c in input().split()])
ans = 0

import bisect
for i in range(N):
  b = B[i]
  end_A = bisect.bisect_left(A, b)
  start_C = bisect.bisect_right(C, b)
  ans += end_A * (N - start_C)

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

import numpy as np
def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=np.zeros([n+1,W+1],dtype=int)
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)
    

### FIXED CODE ###

def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=[[0 for x in range(W+1)] for x in range(n+1)] 
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)
### BUGGY CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc129/tasks/abc129_f

Lが大きいので全探索は不可能
等差数列の桁数ごとに考える？

うしろから考えたほうがよさそうだ？
終項XはA+B*(L-1)　公差は-B の数列t0t1…と考えられる
桁数がkの所だけ考えると寄与の数列u0u1…は

========考察完了=========
桁別に分けて考える
まず桁数がkの奴がいくつあるか、最大の項は何か、それ以前に何桁あるか、が必要
→大きい方から見ていくか

あとは、桁ごとに寄与を計算し、式変形頑張れば解ける
"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

L,A,B,mod = map(int,input().split())

uzero = A+B*(L-1) #u0
ldig  = 0         #u0以前にいくつ桁が存在するか
dignum = len(str(uzero)) #uzeroの桁数

ans = 0
while True:

    if A > uzero: #Aより小さいなら飛ばす
        break
    
    #nは項数
    if 10**(dignum-1) <= A:
        n = (uzero-A)//B+1
    else:
        n = (uzero-A)//B - ((10**(dignum-1)-1)-A)//B


    S = (pow(10,n*dignum)-1) // (pow(10,dignum)-1)
    S %= mod

    Sd = (n-1)*pow(10,n*dignum)-(pow(10,dignum)*(pow(10,(n-1)*dignum)-1)//(pow(10,dignum)-1))
    Sd //= (pow(10,dignum)-1)
    Sd %= mod

    ans += uzero * S * pow(10,ldig,mod) - B * pow(10,ldig,mod)*Sd
    ans %= mod

    #print (uzero , ldig , n ,uzero * S , B * pow(10,ldig,mod)*Sd % mod)

    ldig += dignum * n
    uzero -= B*n
    dignum = len(str(uzero))

print (ans)
    
    


### FIXED CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc129/tasks/abc129_f
=====解説をみた=====

なるほど行列式ね…
繰り返し同じ写像を繰り返す場合、行列式による繰り返し2乗法
を考えるべきなのかもしれんね…

"""

#行列A,Bの積(不可能だとエラー)
def matrix_mul(A,B):

    ans = [ [0] * len(B[0]) for i in range(len(A)) ]

    for ai in range(len(A)):

        for bj in range(len(B[0])):

            now = 0
            for same in range(len(A[0])):
                now += A[ai][same] * B[same][bj]
            ans[ai][bj] = now % mod

    return ans

#行列Aのx乗(当然正方行列じゃないとだめ)
def matrix_pow(A,x):

    B = [[A[i][j] for j in range(len(A[0]))] for i in range(len(A))]
    ans = [[0] * len(A[0]) for i in range(len(A))]
    for i in range(len(A)):
        ans[i][i] = 1

    while x > 0:
        if x % 2 == 1:
            ans = matrix_mul(ans,B)
        B = matrix_mul(B,B)

        x//=2
    return ans

import sys
L,A,C,mod = map(int,input().split())

now = [[0,A,1]]
LA = len(str(A))
LB = len(str(A+C*(L-1)))
B = A+C*(L-1)

if LA==LB:
    np = [[pow(10,LA,mod),0,0],[1,1,0],[0,C,1]]
    k = (B-A)//C+1
    now = matrix_mul(now , matrix_pow(np,k))
    print (now[0][0] % mod)
    sys.exit()

for i in range(LA,LB+1):

    np = [[pow(10,i,mod),0,0],[1,1,0],[0,C,1]]
    #print (now,np)

    if i == LA:
        k = (10**i-1-A)//C+1
        now = matrix_mul(now , matrix_pow(np,k))
    elif i == LB:
        k = (B-A)//C-(10**(i-1)-1-A)//C
        now = matrix_mul(now , matrix_pow(np,k))
    else:
        k = (10**i-1-A)//C - (10**(i-1)-1-A)//C
        now = matrix_mul(now , matrix_pow(np,k))

    #print (i,k,now)
print (now[0][0] % mod)
### BUGGY CODE ###

k,s = map(int,input().split())

ans = 0
for h in range(k+1):
    for i in range(k+1):
        for j in range(k+1):
            if h+i+j==s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())

ans = 0
for i in range(k+1):
    for j in range(k+1):
        if k >= s-i-j >= 0: 
            ans += 1
print(ans)
### BUGGY CODE ###

import math
import statistics

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

for i in range(N):
  a = []
  for index, k in enumerate(li):
    if i == index:
      continue
      
    a.append(k)
    
  print(statistics.median(a))

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
sx = sorted(s)
a = sx[(n//2)-1]
b = sx[n//2]
for i in s:
  if i <= a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
for i in range(m):
  if t.count(t[i])>d.count(t[i]):
    print("NO")
    break
else:
  print("YES")


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
import collections
d=collections.Counter(d)
t=collections.Counter(t)
for i in t.items():
  if i[0] not in d:
    print("NO")
    break
  elif i[0] in d and i[1]>d[i[0]]:
    print("NO")
    break
else:
  print("YES")
### BUGGY CODE ###

N,Q=map(int, input().split())
S=input()
Qs=[list(map(int,input().split())) for i in range(Q)]
for q in range(Q):
    print(S.count('AC',Qs[q][0]-1,Qs[q][1]))

### FIXED CODE ###

N,Q=map(int, input().split())
S=input()
lr=[list(map(int,input().split())) for i in range(Q)]
a=[0]*(N+1)
for i in range(2,N+1):
    if S[i-2:i]=='AC':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]
for q in range(Q):
    print(a[lr[q][1]]-a[lr[q][0]])
### BUGGY CODE ###

n, k,*h = map(int, open(0).read().split())
h=[0]+h
cost = {1: 0, 2: abs(h[2] - h[1])}
for i in range(1, n):
    for di in range(1, k + 1):
        if i + di > n: break
        nc = cost[i] + abs(h[i + di] - h[i])
        if i + di in cost:
            if nc < cost[i + di]:
                cost[i + di] = nc
        else:
            cost[i + di] = nc
print(cost[n])


### FIXED CODE ###

n, k = map(int, input().split())
k = min(n - 1, k)
h = list(map(int, input().split()))
cost = [0 for _ in range(n)]
for i, hi in enumerate(h):
    if i == 0: continue
    st = i - k if i > k else 0
    cost[i] = min([ck + abs(hi - hk) for ck, hk in zip(cost[st:i], h[st:i])])
print(cost[-1])
### BUGGY CODE ###

n = int(input())

numbers = list(map(int, input().split()))
counter = 0

for i in range(len(numbers) - 1):
    sum_i_n = sum(numbers[:i + 1])
    sum_i_n_1 = sum(numbers[:i + 2])

    if sum_i_n == 0:
        numbers[i] += 1
        counter += 1
    if sum_i_n * sum_i_n_1 > 0:
        if sum_i_n_1 > 0:
            numbers[i + 1] -= (sum_i_n_1 + 1)
            counter += sum_i_n_1 + 1
        else:
            numbers[i + 1] += (abs(sum_i_n_1) + 1)
            counter += abs(sum_i_n_1) + 1
if sum(numbers) == 0:
    counter += 1

print(counter)

### FIXED CODE ###

import copy
n = int(input())

numbers = list(map(int, input().split()))
numbers1 = copy.copy(numbers)
counter = 0
counter2 = 0
sum_in = 0
sum_in1 = 0

for i in range(len(numbers)):
    sum_in += numbers[i]
    if i % 2 == 0:
        if sum_in <= 0:
            sub = abs(sum_in) + 1
            sum_in += sub
            numbers[i] += sub
            counter += sub
    else:
        if sum_in >= 0:
            sub = abs(sum_in) + 1
            sum_in -= sub
            numbers[i] -= sub
            counter += sub

for i in range(len(numbers1)):
    sum_in1 += numbers1[i]

    if i % 2 != 0:
        if sum_in1 <= 0:
            sub = abs(sum_in1) + 1
            sum_in1 += sub
            numbers1[i] += sub
            counter2 += sub
    else:
        if sum_in1 >= 0:
            sub = abs(sum_in1) + 1
            sum_in1 -= sub
            numbers1[i] -= sub
            counter2 += sub

print(min([counter2, counter]))
### BUGGY CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

print(ans)













### FIXED CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

print(ans)