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

import re

N = input()
stones = input()
pattern = 'W.*R'
#stoneslist =list(stones)
#result = re.search(pattern,stones)
#if result:
 # print (result.start())
  #print (result.end())
#print(stones[result.start()])
#stoneslist[result.start()]='R'
#stoneslist[result.end()-1]='W'


count =0
while 'WR' in stones:
  if stones.count('WR')>1:
    stoneslist =list(stones)
    result = re.search(pattern,stones)
    stoneslist[result.start()]='R'
    stoneslist[result.end()-1]='W'
    #stones =str(stoneslist)
    stones = "".join(stoneslist)
  else:
    stones = stones.replace('WR','RR',1)
  count+=1
  #print(stones)

#print (stones)
print (count)

### FIXED CODE ###

#import re

N = input()
stones = input()
#pattern = 'W.*R'
#stoneslist =list(stones)
#result = re.search(pattern,stones)
#if result:
 # print (result.start())
  #print (result.end())
#print(stones[result.start()])
#stoneslist[result.start()]='R'
#stoneslist[result.end()-1]='W'

count =0
#while 'WR' in stones:
 # if stones.count('WR')>1:
  #  stoneslist =list(stones)
   # result = re.search(pattern,stones)
    #stoneslist[result.start()]='R'
    #stoneslist[result.end()-1]='W'
    #stones =str(stoneslist)
    #stones = "".join(stoneslist)
  #else:
   # stones = stones.replace('WR','RR',1)
  #count+=1
  #print(stones)

#print (stones)

red = 0
white = 0
for i in range(len(stones)):
  if stones[i] == "R":
    red +=1
for i in range(red):
  if stones[i] =='W':
    white+=1
print (white)
#print (count)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    edges = list()
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((A[i][j], i, j))  # (cost, from, to)
    edges.sort(key=lambda e: e[0])
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


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

s = input()
tmp = [0]
tmpsc = 1
for i in range(len(s)):
    if s[i] == '<':
        tmp.append(tmp[i] + 1)
        tmpsc = 0
    else:
        tmpsc += 1
        if tmp[i] - 1 < 0:
            tmp.append(0)
            for j in range(tmpsc):
                if tmp[i - j] == tmp[i - j + 1]:
                    tmp[i - j] += 1
                else:
                    break
        else:
            tmp.append(0)
print(sum(tmp))

### FIXED CODE ###

s = input()
arr = [0]
for i in range(len(s)):
  if s[i] == '<':
    arr.append(arr[i]+1)
  else:
    arr.append(0)
#print(len(arr))
for i in reversed(range(len(s))):
  if s[i] == '>':
    arr[i] = max(arr[i],arr[i+1]+1)
print(sum(arr))
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

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

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)

### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

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

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

dp = [0]*N
dp[1] = abs(H[1]-H[0])

for i in range(2,N):
    tmp = 10**9
    for j in range(1,min(i,K)+1):
        tmp = min(tmp,abs(H[i]-H[i-j])+dp[i-j])
    dp[i] = tmp

print(dp[-1])


### FIXED CODE ###

N,K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10**20
dp = [0]*N
dp[0] = 0

for k in range(1,N):
    tmp = []
    for i in range(min(k,K)):
        tmp.append(dp[k-i-1]+abs(H[k]-H[k-i-1]))
    dp[k] = min(tmp)
print(dp[-1])
### BUGGY CODE ###

N = int(input())
str = input().split()
A = []
A.append(0)
for i in range(N):
    A.append(int(str[i]))
A.append(0)
SUM = 0
distance = []

for i in range(1,N+2):
    distance.append(abs(A[i] - A[i-1]))

    
buf1 = 0
buf2 = 0
for i in range(1,N+1):
    buf1 = distance.pop(i-1)
    buf2 = distance.pop(i-1)
    #print(A)
    distance.insert(i-1,abs(A[i+1]-A[i-1]))
    print(sum(distance))
    distance.pop(i-1)
    distance.insert(i-1,buf2)
    distance.insert(i-1,buf1)

### FIXED CODE ###

N = int(input())
str = input().split()
A = []
A.append(0)
for i in range(N):
    A.append(int(str[i]))
A.append(0)
SUM = 0
distance = []

for i in range(1,N+2):
    distance.append(abs(A[i] - A[i-1]))
    SUM = SUM + abs(A[i]-A[i-1])

for i in range(1,N+1):
    print(SUM - distance[i] - distance[i-1] + abs(A[i+1] - A[i-1]))
### BUGGY CODE ###

# 整数の入力
N = int(input())
# スペース区切りの整数の入力 リスト
A = list(map(int, input().split()))
count = 0


for j in range(1,100000000):
    odd_flag = True

    while odd_flag:
        for i in range(0,len(A)): #len(A)配列の要素数を整数値で返す
            if A[i] % 2 == 0:
                A[i] = A[i]/2
            else:
                odd_flag = False


count+=1


print(count)

### FIXED CODE ###

def divisible(n):
    ans = 0
    while n % 2 == 0:
        n /= 2
        ans +=1
    return ans
# 整数の入力
N = int(input())
# スペース区切りの整数の入力 リスト
A = list(map(int, input().split()))

ans = min(map(divisible,A))
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
C = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      if L[i]<(L[j]+L[k]) and L[j]<(L[i]+L[k]) and L[k]<(L[i]+L[j]):
        C += 1
        
print(C)

### FIXED CODE ###

from bisect import bisect
from bisect import bisect_left

_ = input()
l = input()
l = sorted(list(map(int, l.split())))
count = 0

for i in range(len(l)):
	for j in range(i+1, len(l)):
		c = l[i]+l[j]
		count += bisect_left(l,c) - (j+1)

print(count)
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jp
#?????\???
#??????????????¨????§?????????¨?????¨?????????????????????????????????????????????????????????
def rrs(quantum, process):
    finished_process = []

    time_queue = Queue()
    name_queue = Queue()
    
    current_time = 0

    for name, time in process:
        time = int(time)
        time_queue.enqueue(time)
        name_queue.enqueue(name)

    while time_queue.data:
        time = time_queue.dequeue()
        name = name_queue.dequeue()
        if time <= quantum:
            current_time += time
            finished_process.append((name, current_time))
        else:
            current_time += quantum
            time_queue.enqueue(time - quantum)
            name_queue.enqueue(name)
            
    return finished_process


class Queue:
    def __init__(self):
        self.data = []

    def enqueue(self, d):
        self.data.append(d)

    def dequeue(self):
        r = self.data[0]
        self.data = self.data[1:]
        return r
    
def main():
    info = input().split()
    n_list = int(info[0])
    quantum = int(info[1])
    target_list = [tuple(input().split()) for i in range(n_list)]
    print("\n".join([p + " " + str(t) for p,t in rrs(quantum, target_list)]))
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jp
#?????\???
#??????????????¨????§?????????¨?????¨?????????????????????????????????????????????????????????
def rrs(quantum, process):
    finished_process = []
    queue = Queue()
    current_time = 0
    i = 0
    
    while not len(finished_process) == len(process):
        
        if i < len(process):
            p_info = process[i]
            i += 1
        else:
            p_info = queue.dequeue()
        time = int(p_info[1])
        name = p_info[0]
        
        if time <= quantum:
            current_time += time
            finished_process.append((name, current_time))
        else:
            current_time += quantum
            queue.enqueue((name, time - quantum))
            
    return finished_process


class Queue:
    def __init__(self):
        self.data = []

    def enqueue(self, d):
        self.data.append(d)

    def dequeue(self):
        r = self.data[0]
        self.data = self.data[1:]
        return r
    
def main():
    info = input().split()
    n_list = int(info[0])
    quantum = int(info[1])
    target_list = [tuple(input().split()) for i in range(n_list)]
    print("\n".join([p + " " + str(t) for p,t in rrs(quantum, target_list)]))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, p):
    used_color = node.edge_color
    for e in node.edge:
        if e != p:
            # 子のノードを取得
            child = tree[e]
            child_used_color = child.edge_color

            # このnodeと子のノードでまだ使っていない色を特定
            unused_colors = colors - (used_color | child_used_color)
            if len(unused_colors) == 0:
                color_num = max(colors) + 1
                colors.add(color_num)
            else:
                color_num = min(unused_colors)

            # このノードと、子のノードに使用ずみの色をマーク
            node.edge_color.add(color_num)
            child.edge_color.add(color_num)

            # 答えを記録
            if a < b:
                ans['{0} {1}'.format(node.num, child.num)] = color_num
            else:
                ans['{0} {1}'.format(child.num, node.num)] = color_num

            # 掘る
            dfs(child, node.num)


N = int(input())
ans = {}
colors = {1}

# treeの初期化
tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)
    if a < b:
        edges.append('{0} {1}'.format(a, b))
    else:
        edges.append('{0} {1}'.format(b, a))

dfs(tree[1], -1)

# print("edges:{}".format(edges))
print(len(colors))
# print(ans)
for edge in edges:
    # print(edge)
    print(str(ans.get(edge)))


### FIXED CODE ###

"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, c = -1 , p = -1):
    k = 1    
    for e in node.edge:
        if e == p:
            continue
        if k == c:
            k += 1
        # 子のノードを取得
        child = tree[e]

        # 答えを記録
        if a < b:
            ans['{0} {1}'.format(node.num, child.num)] = k
        else:
            ans['{0} {1}'.format(child.num, node.num)] = k
        k += 1

        # 掘る
        dfs(child,k - 1, node.num)


N = int(input())
ans = {}
# colors = {1}

# treeの初期化
tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)
    if a < b:
        edges.append('{0} {1}'.format(a, b))
    else:
        edges.append('{0} {1}'.format(b, a))

dfs(tree[1], -1)

# print("edges:{}".format(edges))
# print(max(c))
# print(ans)
count = 0
for node in tree:
    count = max(count, len(node.edge))
print(count)
for edge in edges:
    # print(edge)
    print(str(ans.get(edge)))
### BUGGY CODE ###

import numpy as np
r,g,b,n=map(int,input().split())

lst=[r,g,b]
lst.sort()
r=lst[2]
g=lst[1]
b=lst[0]

rlim=n//r
blim=n//b

blist = np.array([i*b for i in range(blim+1)])

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return False


cnt=0

for i in range(rlim+1):
    glim=(n-i*r)//g
    for j in range(glim+1):
        if binary_search(blist,n-i*r-j*g):
            cnt+=1
print(cnt)

### FIXED CODE ###

r,g,b,n=map(int,input().split())

lst=[r,g,b]
lst.sort()
r=lst[2]
g=lst[1]
b=lst[0]

rlim=n//r
glim=n//g
blim=n//b

"""
blist = [i*b for i in range(blim+1)]

glist = [i*g for i in range(glim+1)]

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return False
"""

cnt=0

for i in range(rlim+1):
    glim=(n-i*r)//g
    for j in range(glim+1):
        if (n-i*r-j*g)%b==0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

#C
#入力
K=int(input())+1


#デバッグ用
def pront(*n):
    if debug==1:
        print(n)
        
debug=1#0:本番,1:デバッグ

#処理
import math as m

Z=[ [ [-1 for i in range(K)] for j in range(K)] for l in range(K)]
def C_1(i,j,k):
    xx=[i,j,k]
    xx.sort()
    if Z[xx[0]][xx[1]][xx[2]]!=-1:
        return Z[xx[0]][xx[1]][xx[2]]
    else:
        Z[xx[0]][xx[1]][xx[2]]=m.gcd(m.gcd(xx[0],xx[1]),xx[2])
        return Z[xx[0]][xx[1]][xx[2]]


x=0
for i in range(1,K):
    for j in range(1,K):
        for k in range(1,K):
            x+=C_1(i,j,k)
print(x)

### FIXED CODE ###

#C
#入力
K=int(input())


#デバッグ用
def pront(*n):
    if debug==1:
        print(n)
        
debug=1#0:本番,1:デバッグ

#処理
import math as m
Z=[ [-1 for i in range(K+1)] for j in range(K+1)]
def C_1(i,j):
    if Z[i][j]!=-1:
        return Z[i][j]
    else:
        x=m.gcd(i,j)
        Z[i][j]=x
        Z[j][i]=x
        return Z[i][j]

x=0
for i in range(1,K+1):
    for j in range(1,K+1):
        y=C_1(i,j)
        if y==1:
            x+=K
        else:
            for k in range(1,K+1):
                x+=C_1(y,k)
print(x)
### BUGGY CODE ###

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

Q = [1 for _ in range(P)]

for i in range(P):
    if A[i]:
        for k in range(P):
            if i == k:
                continue
            Q[i] *= pow(i - k, P - 2, P)
            Q[i] %= P
    else:
        Q[i] = 0

F = [0 for _ in range(P + 1)]
F[0] = 1

for i in range(P):
    tmp = [0 for _ in range(P + 1)]
    for j in range(1, P + 1):
        tmp[j] += F[j - 1]
        tmp[j] %= P
    for j in range(P + 1):
        tmp[j] += F[j] * (-i)
        tmp[j] %= P
    F = tmp

res = [0 for _ in range(P)]

for i in range(P):
    G = [0 for _ in range(P)]
    G[P - 1] = F[P]
    res[P - 1] += Q[i] * G[P - 1]
    res[P - 1] %= P
    for j in range(P - 1)[::-1]:
        G[j] = F[j + 1] + i * G[j + 1]
        G[j] %= P
        res[j] += Q[i] * G[j]
        res[j] %= P

print(*res)

### FIXED CODE ###

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

Q = [1 for _ in range(P)]

for i in range(P):
    if A[i]:
        for k in range(P):
            if i == k:
                continue
            Q[i] *= (i - k)
            Q[i] %= P
        Q[i] = pow(Q[i], P - 2, P)
    else:
        Q[i] = 0

F = [0 for _ in range(P + 1)]
F[0] = 1

for i in range(P):
    tmp = [0 for _ in range(P + 1)]
    for j in range(1, P + 1):
        tmp[j] += F[j - 1]
        tmp[j] %= P
    for j in range(P + 1):
        tmp[j] += F[j] * (-i)
        tmp[j] %= P
    F = tmp

res = [0 for _ in range(P)]

for i in range(P):
    G = [0 for _ in range(P)]
    G[P - 1] = F[P]
    res[P - 1] += Q[i] * G[P - 1]
    res[P - 1] %= P
    for j in range(P - 1)[::-1]:
        G[j] = F[j + 1] + i * G[j + 1]
        G[j] %= P
        res[j] += Q[i] * G[j]
        res[j] %= P

print(*res)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

import fractions

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

d = []
for i in a:
    d.append(abs(i-x))
m = 10**9
for i in d:
    for j in d:
        m = min(m, fractions.gcd(i,j))
print(m)


### FIXED CODE ###

import sys
input=sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

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

m = 10**9
for i in a:
    m = min(m, abs(i-x))

d = make_divisors(m)
d.reverse()
for i in d:
    b = True
    for j in a:
        if abs(j-x) % i != 0:
            b = False
            break
    if b:
        print(i)
        break
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans = (ans + A[i] * A[j]) % int(1e9 + 7)

print(ans)


### FIXED CODE ###

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

s = sum(A)
ans = 0
for i in range(n-1):
    s -= A[i]
    ans = (ans + A[i] * s) % int(1e9 + 7)

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

import itertools

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

for _ in range(H):
    B.append(list(map(int,input().split())))

S = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        S[i][j] = abs(A[i][j] - B[i][j])

S_S = sorted(list(itertools.chain.from_iterable(S)),reverse=True)
MAX_S = sum(S_S[0:H+W-1])
MAX_SS = [[0] * W for _ in range(H)]
DP = [[[False for _ in range(MAX_S+1)] for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            DP[0][0][S[0][0]] = True
            MAX_SS[0][0] = S[0][0]
        else:
            if i - 1 < 0:
                MAX_SS[i][j] = MAX_SS[i][j - 1] + S[i][j]
            elif j - 1 < 0:
                MAX_SS[i][j] = MAX_SS[i - 1][j] + S[i][j]
            else:
                MAX_SS[i][j] = max(MAX_SS[i - 1][j],MAX_SS[i][j - 1]) + S[i][j]

            for d in ((1, 0), (0, 1)):

                if i - d[0] >= 0 and j - d[1] >= 0:
                    for k in range(MAX_SS[i][j] + 1):
                        if k + S[i][j] <= MAX_S:
                            if DP[i-d[0]][j-d[1]][k + S[i][j]]:
                                DP[i][j][k] = True
                        if DP[i-d[0]][j-d[1]][abs(k - S[i][j])]:
                            DP[i][j][k] = True

for i in range(MAX_S+1):
    if DP[H-1][W-1][i]:
        print (i)
        exit(0)

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j] - B[i][j])
    D = [[set() for _ in range(W+1)] for _ in range(H+1)]
    D[0][1] = {0}
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in D[i-1][j] | D[i][j-1]:
                D[i][j].add(abs(k+C[i-1][j-1]))
                D[i][j].add(abs(k-C[i-1][j-1]))

    print(min(D[-1][-1]))


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

# -*- coding: utf-8 -*-
 
n,k = map(int, input().split())
 
################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################
 
if k >= n:
  ans = comb(2*n-1, n, p) % p
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, i, p) % p
    temp2 = comb(n, i, p) % p
    temp = temp * temp2 % p
    ans = (ans + temp) % p
    
print(ans)

### FIXED CODE ###

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

MOD = 10**9 +7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret *= kaijo(n)
  ret %= MOD;
  ret *= gyaku_kaijo(r)
  ret %= MOD;
  ret *= gyaku_kaijo(n-r)
  ret %= MOD;
  return ret




 
n,k = map(int, input().split())
 
################
#p = 10**9 + 7
#def comb(n,k,p):
#  ans = 1
#  for i in range(1,k+1):
#    ans = ans * (n - (i-1)) % p
#    ans = ans * pow(i, p-2, p)
#  return ans
################
 
if k >= n:
  ans = nCr(2*n-1, n) % MOD
else:
  ans = 0
  for i in range(0,k+1):
    temp = (nCr(n-1, i) % MOD) * (nCr(n, i) % MOD) % MOD
    ans = (ans + temp) % MOD
    
print(ans)
### BUGGY CODE ###

n,m = map(int, input().split())
A = sorted(list(map(int, input().split())))
for _ in range(m):
  b,c = map(int,input().split())
  for i in range(b):
    if A[i] < c:
      A[i] = c
  A.sort()
print(sum(A))

### FIXED CODE ###

n,m = map(int, input().split())
List = list(map(int, input().split()))
List.sort()
cand = []
for _ in range(m):
  b,c = map(int,input().split())
  cand.append((b,c))
bc = sorted(cand, key=lambda x: x[1], reverse=True)
i = 0
for b, c in bc:
    while b:
        if i < n and List[i] < c:
            List[i] = c
            b -= 1
        else:
            break
        i += 1
print(sum(List))
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,q = readInts()
    s = input()
    LR = []
    for i in range(q):
        l,r = readInts()
        #print(LR)
        LR.append((l,r))
    for i in range(q):
        #print(i)
        l,r = LR[i]
        l -=1 # zero based index
        S = s[l:r]
        print(S.count('AC'))

if __name__ == '__main__':
  main()


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,q = readInts()
    s = input()
    nya = [0] * (n+1)# 累積和
    for i in range(n):
        if i+1 < n:
            if s[i] == 'A' and s[i+1] == 'C':
                nya[i+1] = nya[i] + 1
            else:
                nya[i+1] = nya[i]
    #print(nya)
    for q_ in range(q):
        l,r = readInts()
        l -=1
        r -=1
        print(nya[r] - nya[l])


if __name__ == '__main__':
  main()