Harryxun/stf_run huggingface dataset:
n,k=map(int, input().split())
    s=input()
    
    ruiwa = [0]

    for i in range(1,len(s)):
        if s[i] != s[i-1]:
            ruiwa.append(i)
    ruiwa.append(n)

    if s[0] == "1":
        ans = ruiwa[1]
        if ((len(ruiwa) - 1) // 2) <= k:
            ans = n
        else:
            for i in range(((len(ruiwa)-1)//2)-k+1):
                ans = max(ans,ruiwa[min(2*k+1+2*i,len(ruiwa)-1)] - ruiwa[2*i])
    else:
        ans = 0
        if len(ruiwa) - 1 - (len(ruiwa) - 1) // 2 <= k:
            ans = n
        else:
            for i in range(len(ruiwa) - 1 - (len(ruiwa)-1)//2 - k + 1):
                ans = max(ans, ruiwa[min(2*k+2*i, len(ruiwa)-1)] - ruiwa[max(0,2*i-1)])

    print(ans)


### FIXED CODE ###

n,k = [int(i) for i in input().split()]
s = input()

if s[0] == "1":
    retu = "whiteblack"
else:
    retu = "blackwhite"


count = 0
pre_person = s[0]
groups = []
for i in range(n):
    person = s[i]

    if person != pre_person:
        groups.append(count)
        count = 0
        pre_person = person
    count += 1
groups.append(count)


maxscore1 = 0
if retu == "whiteblack":
    score1 = 0
    blackgroups = len(groups)//2
    if k < blackgroups:
        start_index = 1
        score1 = groups[start_index-1]
        for j in range(k):
            score1 += groups[start_index+2*j]
            if start_index + 2*j+1 < len(groups):
                score1 += groups[start_index+2*j+1]
        maxscore1 = max(score1, maxscore1)
        for i in range(blackgroups - k):
            score1 -= groups[start_index + 2*i - 1]
            score1 -= groups[start_index + 2*i]
            score1 += groups[start_index + 2*k +2*i]
            if start_index+2*k+1+2*i < len(groups):
                score1 += groups[start_index + 2 * k +1 + 2 * i]
            maxscore1 = max(score1, maxscore1)
    else:
        maxscore1 = n

else:
    score1 = 0
    blackgroups = len(groups) - len(groups)//2
    if k < blackgroups:
        start_index = 0
        score1 = 0
        for j in range(k):
            score1 += groups[start_index+2*j]
            if start_index + 2*j+1 < len(groups):
                score1 += groups[start_index+2*j+1]

        maxscore1 = max(score1, maxscore1)
        for i in range(blackgroups - k):
            if i >=1:
                score1 -= groups[start_index + 2*i - 1]
            score1 -= groups[start_index + 2*i]
            score1 += groups[start_index + 2*k +2*i]
            if start_index+2*k+1+2*i < len(groups):
                score1 += groups[start_index + 2 * k + 1 + 2 * i]

            maxscore1 = max(score1, maxscore1)
    else:
        maxscore1 = n

print(maxscore1)
def how_many_times_divisible(n):
    counter = 0
	
    while n % 2 == 0:
    	n //= 2
        counter +=1
    
    return counter
  
_ = input()
return min(map(lambda x: how_many_times_divisible(int(x)), input().split())



### FIXED CODE ###

def how_many_times_divisible(n):
  counter = 0
  while n % 2 == 0:
    n //= 2
    counter += 1
  return counter
  

_ = input()
print(min(map(lambda x: how_many_times_divisible(int(x)), input().split())))
s = set([int(i) for i in input().split()])
if s.pop() == s.pop() + s.pop():
  print("Yes")
else:
  print("No")

### FIXED CODE ###

l = sorted([int(i) for i in input().split()])
if l[2] == l[1] + l[0]:
  print("Yes")
else:
  print("No")
from scipy.special import comb
n,k=map(int,input().split())
mod=10**9+7
for i in range(1,k+1):
    if i>n-k+1:
        print(0)
    else:
        print( ((comb(k-1, i-1, exact=True) %mod) * (comb(n-k+1,i, exact=True) %mod) ) %mod )

### FIXED CODE ###

from math import factorial as f
n,k=map(int,input().split())
mod=10**9+7
for i in range(1,k+1):
    if i>n-k+1:
        print(0)
    else:
        a= f(k-1)  // (f(i-1) * f(k-i))  %mod
        b= f(n-k+1)// (f(i) * f(n-k-i+1))%mod
        print( a*b %mod )
a,b,k=map(int, input().split())
a,b,k=map(int, input().split())

if a+b<k:
  print(0,0)
elif a<k:
  print(0,b+a-k)
else:
  print(a-k,b)

print("{} {}".format(a, b))

### FIXED CODE ###

a,b,k = map(int, input().split())
 
if a > k:
  print(a-k,b)
  
elif a+b>k:
  print(0,b-k+a)
else:
  print(0,0)
N = input()
lst = input().split(" ")
max  = max(lst)
sum = sum(lst)
if sum - max < max:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

N = input()
lst = input().split(" ")
lst2 = []
for i in lst:
    int_i = int(i)
    #print(int_i)
    lst2.append(int_i)
#print(lst2)
max  = max(lst2)
#print(max)
sum = sum(lst2)
#print(sum)
if sum - max > max:
    print("Yes")
else:
    print("No")
#input()
#import re

s=input()
t=input()
#print(s,t)

flag1=0
for j in range(len(s)-len(t)+1):
  flag=0
  for i in range(len(t)):
    if s[i+j]=='?' or s[i+j]==t[i]:
      flag+=1
  if flag==len(t):
    flag1=1
    s=s[0:j]+t[j-1:j+len(t)]+s[j+len(t):]
    s=s.replace('?','a')
    print(s)
    
if flag1==0:
  print('UNRESTORABLE') 

### FIXED CODE ###

s=input()
t=input()
#print(s,t)

if len(s) < len(t):
    print('UNRESTORABLE') 
elif len(s) == len(t):
  cnt=0
  for i in range(len(s)):
    if s[i] == t[i]:
      cnt+=1
    elif s[i] == '?':
      cnt+=1
  if len(t)==cnt:
    print(t)
  else:
    print('UNRESTORABLE') 
else:
  flag1=0
  for j in range(len(s)-len(t),-1,-1):
    cnt=0
    for i in range(len(t)):
      if s[i+j]==t[i]:
        cnt+=1
      elif s[i+j]=='?':
        cnt+=1
    if cnt==len(t):
      flag1=1
      if j==0:
        s=t+s[len(t):]
      if 0 < j < len(s)-len(t)+1:
        s=s[0:j]+t+s[j+len(t):]
      if j == len(s)-len(t)+1:
        s=s[0:j]+t      
      s=s.replace('?','a')
      print(s)
    
  if flag1==0:
    print('UNRESTORABLE')
N, M = map(int, input().split())
ab_list = sorted([list(map(int, input().split())) for _ in range(M)])

ans = "IMPOSSIBLE"
second_island = []

for a, b in ab_list:
  if a == 1:
    second_island.append(b)

  if b == N:
	if a in second_island:
      ans = "POSSIBLE"
      break

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
sa = set()
sb = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        sb.add(b)
    if b == n:
        sa.add(a)

print('POSSIBLE' if len(sa&sb) != 0 else 'IMPOSSIBLE')
n, m = map(int, input().split())
edges = [[] for i in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.pop()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)


### FIXED CODE ###

n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

from collections import deque

q = deque()

prev = [-1] * n

q.append(0)
while q:
    v = q.popleft()
    for e in edges[v]:
        if prev[e] != -1:
            continue
        prev[e] = v
        q.append(e)

print("Yes")
for val in prev[1:]:
    print(val + 1)
x = int(input())

d = 2

while d < 1+x//2:
  if x%d == 0:
    x += 1
    d = 1
  else:
    if d == 1+x//2:
      ans = x
      break
    else:
      d += 1
print(ans)

### FIXED CODE ###

x = int(input())

d = 2

ans = 2

if x != 2:
  while d <= 1+x//2:
    if x%d == 0:
      x += 1
      d = 2
    else:
      if d == 1+x//2:
        ans = x
        break
      else:
        d += 1
  print(ans)
else:
  print(ans)
A,B,K=map(int, raw_input().split())
l=range(A,B+1)

if len(l)/2>=K:
	for i in l[:K]:
		print i
	for i in l[-K:]:
		print i
elif len(l)/2<K and K<len(l):
	for i in l[:K]:
		print i
	for i in l[ ( K-(2*K-len(l)) )*-1:]:
		print i
else:
	for i in l:
		print i


### FIXED CODE ###

A,B,K=map(int, raw_input().split())
c=set()
for i in range(A,min(B+1,A+K)):
	c.add(i)

for i in range(B,max(A-1,B-K),-1):
	c.add(i)


a=list(c)
a.sort()
for i in a:
	print i
a,b,c=map(int,input().split())
if sorted(list[a,b,c])==[5,5,7]:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a,b,c=map(int, input().split())
if sorted(list((a,b,c)))==[5,5,7]:
  print("YES")
else:
  print("NO")
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
bc=[]
for i in range(M):
  bc.append(list(map(int,input().split())))

bc.sort(key=lambda x:x[1],reverse=True)
nbc=[]
for i in range(M):
  for j in range(bc[i][0]):
    if len(nbc)<=N:
      nbc.append(bc[i][1])

while len(nbc)<=N:
  nbc.append(0)
      
for i in range(N):
  if A[i]>=nbc[i]:
    ind=i
    break

print(sum(nbc[:ind]+A[ind:]))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
bc=[]
for i in range(M):
  bc.append(list(map(int,input().split())))

bc.sort(key=lambda x:x[1],reverse=True)
nbc=[0]*N
inde=0
for i in range(M):
  for j in range(bc[i][0]):
    if inde<=N-1:
      nbc[inde]=bc[i][1]
      inde+=1
      if inde==N:
        break
  if inde==N:
    break
  
ind=N
for i in range(N):
  if A[i]>=nbc[i]:
    ind=i
    break

print(sum(nbc[:ind])+sum(A[ind:]))
X, N = map(int,input().split())
p = list(map(int, input().split()))
#print(p)
#A.sort()
dis = p[0] - X
ans = p[0]
for pi in p :
  if abs(pi-X) < abs(dis):
    ans = pi
    dis = pi - X
    #print("if")
  elif pi-X == -abs(dis):
    ans = pi
    dis = pi - X
  #print(pi-X, abs(pi-X), dis,abs(dis))
print(ans)

### FIXED CODE ###

X, N = map(int,input().split())
if N > 0:
  p = list(map(int, input().split()))
else:
  p=[]
#print(p)
p.sort()
#dis = p[0] - X
ans_1 = X
ans_2 = X
for i in range(N) :
  pi = p[i]
  if pi == ans_1:
    ans_1 += 1

p.reverse()
for i in range(N) :
  pi = p[i]
  if pi == ans_2:
    ans_2 -= 1

ans = X
if abs(ans_1 - X) < abs(ans_2 - X):
  ans = ans_1
elif ans_1 - X == -abs(ans_2 - X):
  ans = ans_1
else:
  ans = ans_2
print(ans)
a = x**3
print(a)

### FIXED CODE ###

x = input()
print(x*x*x)
N = int(input())

if N>=3:  　　　　　   #生徒数が３人以上が必須条件
    print(int(N/3))　 #生徒数を最低条件の３人で割る
else:
    print(0)

### FIXED CODE ###

N = int(input())

x=N//3              #生徒の人数で割ったものがグループ数
                    #//で小数点以下を削除している
print(x)
n,m = map(int,input().split())
s = input()

now = n
ans_rev = []
while(now != 0):
    for i in range( now-m,now+1):
        if(i == now):
            print(-1)
            exit()
        if(s[i] == '1'):
            continue

        ans_rev.append(now - i)
        now = i
        break

print(' '.join(map(str, ans_rev[::-1])))

### FIXED CODE ###

n,m = map(int,input().split())
s = input()

s_0 = []
for i in range(n+1):
    if(s[i] == '0'):
        s_0.append(i)

# 二分木
import bisect

now = n
ans_rev = []
while(now != 0):
    next_i = bisect.bisect_left(s_0, now-m)
    next = s_0[next_i]
    if(now == next):
        print(-1)
        exit()
    ans_rev.append(now-next)
    now = next

print(' '.join(map(str, ans_rev[::-1])))
# -*- coding: utf-8 -*-

import math

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

ans = a[0]
for a_val in a:
    ans = math.gcd(ans, a_val)

print(ans)

### FIXED CODE ###

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

def gcd(a, b):
    big, small = max(a, b), min(a,b)
    if big % small == 0:
        return small
    return gcd(small, big%small)


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

ans = a[0]
for a_val in a:
    ans = gcd(ans, a_val)

print(ans)
def f03():
    n=int(input())
    s, t=map(str, input().split())
    print(*[s[i]+t[i] for i in range(n)], seq='')
f03()

### FIXED CODE ###

def f03():
    n=int(input())
    s, t=map(str, input().split())
    print(''.join([s[i]+t[i] for i in range(n)]))
f03()
a,b = map(int,input().split())
from fractions import gcd
c = math.gcd(a,b)
answer = a*b/c
print(int(answer))

### FIXED CODE ###

a,b = map(int,input().split())
from fractions import gcd
c = gcd(a,b)
answer = a*b/c
print(int(answer))
n = int(input())
li = list(map(int, input().split()))

ans = 0
for i in range(1, n-1):
  if li[i-1] > li[i] and li[i+1] < li[i]:
    ans += 1
  if if li[i-1] < li[i] and li[i+1] > li[i]:
    ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(1, n-1):
  if li[i-1] > li[i] and li[i+1] < li[i]:
    ans += 1
  if li[i-1] < li[i] and li[i+1] > li[i]:
    ans += 1
print(ans)
A, B, K = map(int, input().split())

yakusuu=[]
for i in range(1,A):
  if A% i == 0:
    yakusuu.append(i)
  
for j in range(1,B):
  if B%j == 0:
    yakusuu.append(j)

print(sorted(yakusuu)[K+1])

### FIXED CODE ###

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

yakusuu=[]
yakusuuA = []
yakusuuB = []
for i in range(1,A+1):
  if A% i == 0:
    yakusuuA.append(i)
  
for j in range(1,B+1):
  if B%j == 0:
    yakusuuB.append(j)
    
yakusuu = list(set(yakusuuA) & set(yakusuuB))
yakusuu.append(1)     
print(sorted(yakusuu, reverse=True)[K-1])
H,W = map(int,input().split())
mine_map = [list(input().split()) for x in range(H)]
for i in range(H):
  for j in range(W):
    count = 0
    if mine_map[i][j] == ".":
      for k in range(-1,2):
        for l in range(-1,2):
          if i+k >= 0 and i+k < H and j+l >= 0 and j+l < W:
            if mine_map[i+k][j+l] == "#":
              count += 1
      mine_map[i][j] = count
    print(mine_map[i][j],end="")
  print()

### FIXED CODE ###

H,W = map(int,input().split())
mine_map = [list(input()) for x in range(H)]
for i in range(H):
  for j in range(W):
    count = 0
    if mine_map[i][j] == ".":
      for k in range(-1,2):
        for l in range(-1,2):
          if i+k >= 0 and i+k < H and j+l >= 0 and j+l < W:
            if mine_map[i+k][j+l] == "#":
              count += 1
      mine_map[i][j] = count
    print(mine_map[i][j],end="")
  print()
a,b,c=int(input()),int(input()),int(input())
if a+b==c or a+c==b or b+c==a:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c=map(int,input().split())
if a+b==c or a+c==b or b+c==a:
  print("Yes")
else:
  print("No")
W,H,x,y,r = map(int,input().split())
print('No' if (x-r)<0 or (x+r)>w or (y-r)<0 or (y+r)>h else 'Yes')

### FIXED CODE ###

W,H,x,y,r = map(int,input().split())
print('Yes' if x + r <= W and y - r >= 0 and x - r >= 0 and y + r <= H else 'No')
N, T = map(int, input().split())
r = [tuple(map(int, input().split())) for _ in range(N)]
f = [(c, t) for c, t in r if t <= T]
print(min(f, key=lambda x: x[0])[0])


### FIXED CODE ###

N, T = map(int, input().split())
r = [tuple(map(int, input().split())) for _ in range(N)]
f = [(c, t) for c, t in r if t <= T]
if len(f)==0:
  print('TLE')
else:
  print(min(f, key=lambda x: x[0])[0])
x,a,b=[int(input() for i in range(3))]
print((x-a)%b)

### FIXED CODE ###

x,a,b=(int(input()) for _ in range(3))
print((x-a)%b)
def check(pair,m,x):
  l = len(pair)
  sum = 0
  
  for i in range(1,m):
    p = 0
    for j in range(l):
      p += pair[j][i]
    
    if(p < x):
      return -1
    
  for e in pair:
    sum += e[0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
min = -1
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
      
  sum = check(pair,m,x)
  if sum != -1:
    if min == -1:
      min = sum
    elif min > sum:
      min = sum
    
print(min)

### FIXED CODE ###

n,k = (int(x) for x in input().split())
a = tuple([int(x) for x in input().split()])
 
c = [0] + [-1]*(n)
l = [1]
now = 1
dupl = -1

for i in range(k):
  now = a[now - 1]
  c[now - 1] += 1
   
  if c[now - 1] == 1:
    dupl = now
    break
  else:
    l.append(now)
    
if dupl == -1:
  print(now)
  exit()
       
notloop = l.index(dupl)
length = len(l)-notloop
print(l[(k-notloop)%length+notloop])
n = int(input())
if n == 7 or n == 5 or n == 3:
    print(YES)
else:
    print(NO)

### FIXED CODE ###

n = int(input())
if n == 7 or n == 5 or n == 3:
  print("YES")
else:
  print("NO")
N = int(input())
A = list(map(int, input().split()))

p_num = [0]*9

for a in A:
    p_num[a//400] += 1
    
ans = 0
for p in p_num[:-1]:
    if p:
        ans +=1
        
ans_min = ans
ans_max = ans + p_num[-1]

print(ans_min, ans_max)

### FIXED CODE ###

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

p_num = [0]*9

for a in A:
    if a<3200:
        p_num[a//400] += 1
    else:
        p_num[-1] += 1
    
ans = 0
for p in p_num[:-1]:
    if p:
        ans +=1
        
ans_min = max(ans,1) 
ans_max = ans + p_num[-1]

print(ans_min, ans_max)
def cal():
  n=int(input())
  arr=list(map(int,input.split()))
  prod=1
  for i in range(0,n):
    prod*=arr[i]
    if(prod>=1000000000000000000):
      print(-1)
      return
  print(prod)
  return

cal()

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
    
  print(prod)
main ()
#真に大切なのは中間点となる要素
N, M = map(int, input().split())
an = set()
nb = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.append(b)
    elif b == N:
        nb.append(a)

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')

### FIXED CODE ###

#真に大切なのは中間点となる要素
N, M = map(int, input().split())
an = set()
nb = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.add(b)
    elif b == N:
        nb.add(a)

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')
N=int(input())
l=[]
for i in range(N):
    l.append(int(input()))
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
print(lcm_list(l))

### FIXED CODE ###

N=int(input())
l=[]
for i in range(N):
    l.append(int(input()))
import fractions
from functools import reduce
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
print(lcm_list(l))
s=input()
print(s[0] + str(len(s-2))+ s[-1])

### FIXED CODE ###

s=input()
print(s[0] + str(len(s)-2)+ s[-1])
from math import log2
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
B = max(max(Ai) for Ai in A)
if M == 1:
    if N == 1 or all(A[i][0] < A[i+1][0] for i in range(N-1)):
        print("0")
    else:
        print("-1")
    exit(0)
logB = log2(B)
logBi = int(logB)
INF = 10**18
def gen(P, t):
    if t <= logB:
        for k in range(t):
            for i in range(M-1):
                P[i+1] += P[i]
    else:
        for k in range(t):
            for i in range(min(logBi+2, M)):
                P[i+1] += P[i]
        for i in range(logBi+2, M):
            P[i] = INF
T = [0]*N
ans = 0
P = [0]*M
for i in range(N-1):
    a0, a1 = A[i][:2]
    b0, b1 = A[i+1][:2]
    if a0 < b0:
        continue
    if a0 > b0:
        ans = -1
        break
    t0 = T[i]
    v = max(t0*a0 + a1 - b1, 0)
    if v % b0 > 0:
        T[i+1] = t1 = (v + b0-1) // b0
        ans += t1
        continue

    t1 = v // b0
    if t0 <= t1:
        P[:] = A[i+1]
        gen(P, t1 - t0)
        if P <= A[i]:
            t1 += 1
    else:
        P[:] = A[i]
        gen(P, t0 - t1)
        if A[i+1] <= P:
            t1 += 1
    T[i+1] = t1
    ans += t1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
from math import log2
from itertools import accumulate
N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for i in range(N)]
B = max(max(Ai) for Ai in A)
if M == 1:
    if N == 1 or all(A[i][0] < A[i+1][0] for i in range(N-1)):
        print("0")
    else:
        print("-1")
    exit(0)
logB = log2(B)
logBi = int(logB)
INF = 10**18
INFL = [INF]*(M - logBi-2)
def gen(P, t, L = min(logBi+2, M)):
    if t <= logB:
        for k in range(t):
            P[:] = accumulate(P)
    else:
        V = [1]*L
        for k in range(1, L):
            V[k] = V[k-1] * (t + k - 1)//k

        for i in range(L-1, 0, -1):
            P[i] += sum(P[j] * V[i-j] for j in range(i))
        if logBi+2 < M:
            P[logBi+2:] = INFL
T = [0]*N
ans = 0
P = [0]*M
for i in range(N-1):
    a0, a1 = A[i][:2]
    b0, b1 = A[i+1][:2]
    if a0 < b0:
        continue
    if a0 > b0:
        ans = -1
        break
    t0 = T[i]
    v = max(t0*a0 + a1 - b1, 0)
    if v % b0 > 0:
        T[i+1] = t1 = (v + b0-1) // b0
        ans += t1
        continue

    t1 = v // b0
    if t0 <= t1:
        P[:] = A[i+1]
        gen(P, t1 - t0)
        if P <= A[i]:
            t1 += 1
    else:
        P[:] = A[i]
        gen(P, t0 - t1)
        if A[i+1] <= P:
            t1 += 1
    T[i+1] = t1
    ans += t1
print(ans)
a,v=(int(x) for x in input().split())
b,w=(int(x) for x in input().split())
t = int(input())

distance = abs(a-b)
sa = v - w
if distance%sa == 0 and distance < t*sa:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a,v=(int(x) for x in input().split())
b,w=(int(x) for x in input().split())
t = int(input())
 
distance = abs(a-b)
sa = v - w
 
if distance <= t*sa:
  print('YES')
else:
  print('NO')
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    list[i] =tmp
    for d in range(W):
        dict[list[i][d]] = str(i)+' '+str(d)
cost = {}

def calcost(L,R,D):
    if int(R)<=D or (int(R)-int(L))<D:
        return 0
    else:
        if str(int(R)-D) in cost:
            return cost[str(int(R)-D)] + calcost(L,str(int(R)-D),D)
        else:
            posi1 = dict[R].split()
            posi2 = dict[str(int(R)-D)].split()
            costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
            cost[str(int(R)-D)] = costs
            return costs + calcost(L,str(int(R)-D),D)

Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(calcost(tmp[0],tmp[1],D))

### FIXED CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))
N,Q=map(int, input().split())
S = input()

l = [0] * N
r = [0] * N

for i in range(Q):
    l[i], r[i] = map(int, input().split())

for j in range(Q):
    print(S[l[j]-1:r[j]].count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])