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

# Problem A - Frog 2 - Algoritmos e Grafos - MATA52
def frog2(n, h, k_max):
    global stones
    stones[0] = 0
    stones[1] = 0
    for i in range(1, n):
        for j in range(1, k_max):
            if i + j < n:
                w1 = stones[i + j]
                w2 = abs(h[i + j] - h[i])
                stones[i + j] = min(w1, stones[i] + w2)
            else:
                break
    return stones[n - 1]

inf = input()
inf = inf.split()
n = int(inf[0]) + 1
k_max = int(inf[1]) + 1
h = [int(x) for x in input().split()]
h = [0] + h

stones = [float("inf")] * n
print(frog2(n, h, k_max))

### FIXED CODE ###

def main():
    infinity = 1e10

    n, k, height = getInputs()

    cost = [infinity] * n
    cost[0] = 0
    cost[1] = abs(height[0] - height[1])

    for i in range(2, n):
        for j in range(i - 1, i - k - 1, -1):
            if j >= 0:
                cost[i] = min(cost[i], cost[j] + abs(height[i] - height[j]))

    print(cost[-1])

def getInputs():
    n, k = map(lambda x: int(x), input().split())
    height = tuple(map(lambda x: int(x), input().split()))

    return n, k, height

main()
### BUGGY CODE ###

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

while len(A)>1:
    if A[0]==A[1]:
        A=A[1:]
    else:
        res=(A[1]>A[0])
        for i in range(len(A)-1):
            if (A[i+1]<A[i] and res) or (A[i+1]>A[i] and not res):
                A=A[i+1:]
                counter+=1
                break


print(counter)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
counter=1
res=0
for i in range(len(A)-1):
    if (A[i+1]<A[i] and res>0) or (A[i+1]>A[i] and res<0):
        counter+=1
        res=0
    elif A[i+1]!=A[i]:
        res=A[i+1]-A[i]


print(counter)
### BUGGY CODE ###

##C - Sum of product of pairs
##累積和
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N-1):
    ans += A[i]*sum(A[i+1:])
print(ans % (10**9+7))

### FIXED CODE ###

##C - Sum of product of pairs
##累積和
N = int(input())
A = list(map(int,input().split()))
S = sum(A)
ans = 0
for i in range(N-1):
    ans += A[i]*(S - A[i])
    S -= A[i]
print(ans % (10**9+7))
### BUGGY CODE ###

# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

### FIXED CODE ###

# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)
### BUGGY CODE ###

n = int(input())
s = list(input())
mn = 300000

e = []
w = []
for c in s:
    if c == "E":
        e.append(1)
        w.append(0)
    else:
        e.append(0)
        w.append(1)

for i in range(n):
    mn = min(mn, sum(w[:i])+sum(e[i+1:]))
print(mn)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = s[1:].count("E")
tmp = ans

for i in range(1, n):
    if s[i]=="E": tmp -= 1
    if s[i-1]=="W": tmp += 1
    ans = min(tmp, ans)
print(ans)
### BUGGY CODE ###

import collections

n = int(input())

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

a.sort()

dp = [True] * n

for i in range(len(a) - 1):
    if dp[i] == True:
        for j, x in enumerate(a[i+1:], 1):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False
        
        if a[i] == a[i + 1]:
            dp[i] = False

print(sum(dp))

### FIXED CODE ###

n = int(input())

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

a.sort()

dp = [True] * (a[-1] + 1)

ans = 0

m = a[-1]

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and dp[x]:
        ans += 1
    for b in range(x, m + 1, x):
        dp[b] = False

if dp[a[-1]]:
    ans += 1

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

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

pair_count = 0

for i in range(N):
    for j in range(i+1,N):
        if abs(i-j) == A[i]+A[j]:
            pair_count+=1

print(pair_count)

### FIXED CODE ###

'''
i<j としたとき求めたいのは
i + Ai = j - Aj の組み合わせの数
そこで各々の Li = i + Ai, Ri = i - Aiを計算し辞書型で保持しておく
'''
from collections import defaultdict

N =int(input())
A = list(map(int,input().split()))
Li = defaultdict(int)
Ri = defaultdict(int)
for i,a in enumerate(A,start=1):
    Li[i+a] += 1
    Ri[i-a] += 1

ans = 0
for k,v in Li.items():
    if k in Ri:
        ans += Li[k]*Ri[k]

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

# 2020/05/03
# AtCoder Beginner Contest 166 - D

# Input
x = int(input())

# Calc
eflg = False
for a in range(30000):
    wk_a = a ** 5
    for b in range(30000):
        if wk_a - (b ** 5) == x:
            ans1 = a
            ans2 = b
            eflg = True
            break

        if wk_a - (-b ** 5) == x:
            ans1 = a
            ans2 = -b
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ans1, ans2)


### FIXED CODE ###

# 2020/05/03
# AtCoder Beginner Contest 166 - D

# Input
x = int(input())

# Calc
eflg = False
for a in range(200):
    wk_a = a ** 5
    for b in range(200):
        if wk_a - (b ** 5) == x:
            ans1 = a
            ans2 = b
            eflg = True
            break

        if wk_a - (-b ** 5) == x:
            ans1 = a
            ans2 = -b
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ans1, ans2)
### BUGGY CODE ###

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

for h in range(H):
    SW.append([])
    c = 0
    for w in range(W):
        if S[h][w] == '#':
            if c != 0:
                for _ in range(c):
                    SW[h].append(c)
            SW[h].append(0)
            c = 0
        else:
            c += 1
    for _ in range(c):
        SW[h].append(c)

for w in range(W):
    SH.append([])
    c = 0
    for h in range(H):
        if S[h][w] == '#':
            if c != 0:
                for _ in range(c):
                    SH[w].append(c)
            SH[w].append(0)
            c = 0
        else:
            c += 1
    for _ in range(c):
        SH[w].append(c)

ans = -1
for h in range(H):
    for w in range(W):
        ans = max(ans, SW[h][w] + SH[w][h] - 1)

print(ans)


### FIXED CODE ###

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

for h in range(H):
    SW.append([])
    c = 0
    for w in range(W):
        if S[h][w] == '#':
            if c != 0:
                for _ in range(c):
                    SW[h].append(c)
            SW[h].append(0)
            c = 0
        else:
            c += 1
    for _ in range(c):
        SW[h].append(c)

for w in range(W):
    SH.append([])
    c = 0
    for h in range(H):
        if S[h][w] == '#':
            if c != 0:
                for _ in range(c):
                    SH[w].append(c)
            SH[w].append(0)
            c = 0
        else:
            c += 1
    for _ in range(c):
        SH[w].append(c)

ans = -1
for h in range(H):
    for w in range(W):
        ans = max(ans, SW[h][w] + SH[w][h] - 1)

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

from collections import defaultdict
d = defaultdict(int)
N = int(input())
A = [int(i) for i in input().split()]
a = A.count
for i in set(A):
  d[i] = a(i)
cnt = 0
for i, j in d.items():
  if i < j:
    cnt += j-i
  elif i > j:
    cnt += j   
print(cnt)

### FIXED CODE ###

N = int(input())
A = sorted(int(i) for i in input().split())+[0]
cnt, ans = 0, 0
a = A[0]
for i in range(len(A)):
  if a == A[i]:
    cnt += 1
  elif a != A[i]:
    if cnt < a:
      ans += cnt
    elif cnt > a:
      ans += cnt-a
    a = A[i]
    cnt = 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
l = len(a)
for i in range(l-1):
    for j in range(i,l):
        ans += (a[i]^a[j]) % mod
print(ans%mod)

### FIXED CODE ###

import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def myinput():
    return map(int,readline().split())

n = int(readline())
a = list(myinput())
mod = 10**9 + 7
ans = 0

for j in range(60):
    k = 2**j
    one = 0
    zero = 0
    for i in range(n):
        if (a[i]&k):
            one += 1
        else:
            zero += 1
    ans_bit = zero * one
    ans += (ans_bit)*(2**j) 
    ans %= mod   

print(ans%mod)
### BUGGY CODE ###

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

babies = [(a, i) for i, a in enumerate(a)]

babies.sort(reverse=True)

dp = [[0] * (n+1) for i in range(n+1)]

ans = 0

for l in range(n):
    for r in range(n):
        if l + r == n:
            ans = max(ans, dp[l][r])
            break
        activeness, ind = babies[l+r]
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(ind - l) * activeness)
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] + abs(ind - (n-1-r)) * activeness)

print(ans)

### FIXED CODE ###

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

babies = [(a, i) for i, a in enumerate(a)]

babies.sort(reverse=True)

dp = [[0] * (n+1) for i in range(n+1)]

ans = 0

for l in range(n):
    for r in range(n):
        if l + r == n:
            ans = max(ans, dp[l][r])
            break
        activeness, ind = babies[l+r]
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(ind - l) * activeness)
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] + abs(ind - (n-1-r)) * activeness)

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

from itertools import *
from collections import *
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
v=[[False for j in range(w)] for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
aa=0
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if v[nx][ny]:
                continue
            v[nx][ny]=True
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if ans[nx][ny]>aa:
                    aa=ans[nx][ny]
                if (nx,ny) not in q:
                    q.append((nx,ny))
print(aa)

### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
print(ans)
### BUGGY CODE ###

L = input()
p = 10 ** 9 + 7
ans = 0
b = 0
while len(L) > 0:
  ans += (3 ** (len(L) - 1)) * (2 ** b)
  ans %= p
  L = L[1:]
  b += 1
  if L == '':
    break
  while L and L[0] == '0':
    L = L[1:]
ans += 2 ** b
ans %= p
print(ans)

### FIXED CODE ###

L = input()
p = 10 ** 9 + 7
l = len(L)
ones = 0
cnt = 1
two = [1] * l
three = [1] * l
for i in range(1, l):
  two[i] = two[i - 1] * 2 % p
  three[i] = three[i - 1] * 3 % p
for i, b in enumerate(L):
  if b == '1':
    left = two[ones]
    right = (three[l - 1 - i] + 1) % p
    cnt += left * right
    cnt %= p
    ones += 1
print(cnt)
### BUGGY CODE ###

import collections

n = int(input())
s = input()
cnt = 0
for i in range(n)[::-1]:
  ch = s[i:]
  c = collections.Counter(ch)
  tmp_cnt = 1
  for k,v in c.items():
    if k != s[i]:
      tmp_cnt *= (v+1)
  cnt += tmp_cnt % (10**9+7)
print(cnt% (10**9+7))

### FIXED CODE ###

import collections

n = int(input())
s = input()
cnt = 0
dictionary = {}

for i in range(n)[::-1]:
  if s[i] in dictionary.keys():
    dictionary[s[i]] += 1
  else:
    dictionary[s[i]] = 1
  ch = s[i:]
  tmp_cnt = 1
  for k,v in dictionary.items():
    if k != s[i]:
      tmp_cnt *= (v+1)
  cnt += tmp_cnt % (10**9+7)
print(cnt % (10**9+7))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict

def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    MAX = 10**16
    minCurrent = defaultdict(lambda :MAX)
    minCurrent[0] = 0
    currentPos = [0]
    heapq.heapify(currentPos)
    visited = set()
    while len(currentPos) > 0:
        cp = heapq.heappop(currentPos)
        if cp in visited:
            continue
        if cp > H:
            break
        visited.add(cp)
        cc = minCurrent[cp]
        for i in range(N):
            heapq.heappush(currentPos, cp + A[i])
            minCurrent[cp + A[i]] = min(minCurrent[cp + A[i]],cc+B[i])
    c = MAX
    for key in minCurrent:
        if key >=H:
            c = min(c,minCurrent[key])
    print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [10**16]*(H+1)
    dp[0] = 0
    positions = [0]
    for i in range(len(dp)):
        c = dp[i]
        for j in range(N):
            ni = min(H, i+A[j])
            dp[ni] = min(dp[ni], c+B[j])
    print(dp[-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)


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

q = int(input())
a = [input() for _ in range(q)]
dic = {}

for i in a:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
keys = [k for k, v in dic.items() if v == max(dic.values())]
keys_s = sorted(keys)
for i in keys_s:
    print(i)


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

q = int(input())
a = [input().rstrip() for _ in range(q)]

dic = collections.Counter(a)

ma = max(dic.values())
keys = [k for k, v in dic.items() if v == ma]
keys_s = sorted(keys)
for i in keys_s:
    print(i)
### BUGGY CODE ###

import sys

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_stu_Num_int = [int(s) for s in list_stu_Num]
list_attend_stu = []
list_stu_Serial_Num = list(range(1, Num + 1))
for i in list_stu_Serial_Num:
    l = list_stu_Num_int.index(i) + 1
    list_attend_stu.append(l)
print(*list_attend_stu)

### FIXED CODE ###

import sys
import numpy as np

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_stu_Num_int = [int(s) for s in list_stu_Num]
print(*np.argsort(list_stu_Num_int) + 1)
### BUGGY CODE ###

h, w, m = map(int, input().split())
hw = []
h_cnt = [0] * h
w_cnt = [0] * w
hw = []
hw_set = set()
for _ in range(m):
    r, c = map(int, input().split())
    r -= 1
    c -= 1
    h_cnt[r] += 1
    w_cnt[c] += 1
    hw.append((r, c))
    hw_set.add((r, c))
mh = max(h_cnt)
mw = max(w_cnt)
ans = mh + mw
is_exist = False
for i in range(h):
    if h_cnt[i] != mh:
        continue
    for j in range(w):
        if w_cnt[j] == mw:
            if not (i, j) in hw_set:
                is_exist = True
                print(ans)
                exit()
print(ans - 1)


### FIXED CODE ###

h, w, m = map(int, input().split())
hw = []
h_cnt = [0] * h
w_cnt = [0] * w
hw = []
hw_set = set()
for _ in range(m):
    r, c = map(int, input().split())
    r -= 1
    c -= 1
    h_cnt[r] += 1
    w_cnt[c] += 1
    hw.append((r, c))
    hw_set.add((r, c))
mh = max(h_cnt)
mw = max(w_cnt)
cand_r = []
for i in range(h):
    if h_cnt[i] == mh:
        cand_r.append(i)
cand_c = []
for j in range(w):
    if w_cnt[j] == mw:
        cand_c.append(j)
ans = mh + mw
for i in cand_r:
    for j in cand_c:
        if not (i, j) in hw_set:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

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

ans = 0
for i in range(10**3):
    mm = 0
    num = str(i).zfill(3)
    for j in range(N):
        if num[mm]==S[j]:
            mm += 1
        if mm==3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(10**3):
    mm = 0
    num = str(i).zfill(3)
    for j in range(N):
        if num[mm]==S[j]:
            mm += 1
        if mm==3:
            ans += 1
            break
print(ans)
### BUGGY CODE ###

def b_len(v):
    return len(bin(v)[2:])


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

cs = [0]
for aa in a:
    cs.append(cs[-1] + aa)

ps = []
for i in range(1, n + 1):
    for j in range(i):
        ps.append(cs[i] - cs[j])

ps = sorted(ps, reverse=True)

pw = b_len(ps[k - 1])
MOD = 2 ** pw

nps = [set() for _ in range(pw)]
for i in range(len(ps)):
    t = ps[i] % MOD
    for j in range(pw):
        if 1 << j & t:
            nps[j].add(i)

ans = 0
buf = set(range(len(ps)))
for j in range(pw)[::-1]:
    if len(nps[j]) >= k:
        x = buf & nps[j]
        if len(x) >= k:
            buf = x
            ans += 2 ** j

print(ans)

### FIXED CODE ###

from math import log, ceil

n, k = map(int, input().split())
a = tuple(map(int, input().split()))

A_MAX = 10 ** 9
MAX_BIT_LENGTH = ceil(log(A_MAX * n, 2))

cs = [0]
t = 0
for aa in a:
    t += aa
    cs.append(t)

ps = []
for r in range(1, n + 1):
    for l in range(r):
        ps.append(cs[r] - cs[l])

ans = 0
for b in range(MAX_BIT_LENGTH)[::-1]:
    cnt = 0
    t = ans + (1 << b)
    for p in ps:
        if p & t == t:
            cnt += 1
            if cnt == k:
                ans = t
                break

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

#C

K=int(input())
ans=-1
for i in range(1,10**8):
    tmp=int("7"*i)
    if tmp%K==0:
        ans=i
        break
print(ans)

### FIXED CODE ###

#C

K=int(input())
ans=-1
if K==1:
    ans=1
elif K==2 or K==5 or K==10:
    ans=-1
else:
    p=0
    for i in range(1,K+1):
        p = (p*10+7)%K 
        #print(i,p)
        if p==0:
            ans=i
            break

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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
LR = []
for i in range(Q):
    LR.append(LI())
#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

for l, r in LR:
    tmp = S[l-1:r]
    print(tmp.count('AC'))



### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx] == 'A':
        if S[sidx+1] == 'C':
            ACs.append(sidx)

#  print(ACs)

LR = []
for i in range(Q):
    LR.append(LI())

#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for l, r in LR:
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    print(end-start)