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

import itertools
a,b=map(int,input().split())
L=list(map(int,input().split()))
L=list(itertools.combinations(L, b))
K=[max(i)-min(i) for i in L]
print(sum(K)%1000000007)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7
N = 10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,K=map(int,input().split())
L=list(map(int,input().split()))
L=sorted(L)
s=0
for i in range(N-K+1):
  s+=(cmb(N-i-1,K-1,mod)*(L[N-1-i]-L[i]))%mod
print(s%mod)
### BUGGY CODE ###

X = int(input())
result = []
for i in range(X,X*2):
    if i > 1:
        for j in range (2, i):
            if (i % j) == 0:
                break
        else:
            result.append(i)
print (min(result))

### FIXED CODE ###

X = int(input())
result = []
for i in range(X,X*2):
    for j in range (2,i):
        if (i % j) == 0:
            break
    else:
            result.append(i)
            a = i
            break
print (a)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)//2
m=S
for n in range(N//2):m-=A[2*n+1]
ans=str(2*m)
for i in range(N-1):
    ans=ans+" "+str(2*(A[i]-m))
    m=A[i]-m
print(ans)

### FIXED CODE ###

from collections import deque
N=int(input())
A=list(map(int,input().split()))
D=deque(A)
m=sum(A)//2
for n in range(N//2):m-=A[2*n+1]
ans=str(2*m)
for _ in range(N-1):
    a=deque.popleft(D)-m
    ans+=" "+str(a*2)
    m=a
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from heapq import heappop,heappush
import math

xs,ys,xt,yt = map(int,input().split())
n = int(input())

v = [(xs,ys,0)]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append((x,y,r))
v.append((xt,yt,0))

def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[] for i in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i != j:
            d_ij = dd(v[i],v[j])
            edges[i].append((d_ij,j))
            edges[j].append((d_ij,i))

def dijkstra(s,n,edges):
    #edges[source] = [(cost_1,target_1),(cost_2,target_2),...]
    #import 'heap'
    d = [float('inf')] * n
    d[s] = 0
    q = [[d[s],s]]
    while q:
        dist_u, u = heappop(q)
        for c, v in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q,[d[v],v])
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+2):
    for j in range(i+1,n+2):
        edges[i][j] = dd(v[i],v[j])
        edges[j][i] = dd(v[i],v[j])

def dijkstra(s,n,edges):
    #edges[i][j] : the cost of i→j
    #import 'heap'
    d = [float('inf') for _ in range(n)]
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])
### BUGGY CODE ###

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

max_dice = 0
for i in range(K-1, N):
    tmp_dice = 0
    for i in range(i - K + 1, i + 1):
        tmp_kitai = 0
        for j in range(p[i]):
            tmp_kitai += (j + 1)
        tmp_kitai = tmp_kitai / p[i]
        tmp_dice += tmp_kitai
    if tmp_dice > max_dice:
        max_dice = tmp_dice
print(max_dice)

### FIXED CODE ###

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

dp = [0] * (N)
dp_sub = [0] * (N)

dp[0] = (p[0] + 1) / 2
dp_sub[0] = (p[0] + 1) / 2

for i in range(1, K):
    dp_sub[i] = (p[i] + 1) / 2
    dp[i] = dp[i - 1] + dp_sub[i]

for i in range(K, N):
    dp_sub[i] = (p[i] + 1) / 2
    dp[i] = dp[i - 1] + dp_sub[i] - dp_sub[i-K]
    
print(max(dp))
### BUGGY CODE ###


from bisect import bisect_left
from itertools import accumulate

def resolve():
    def getCount(x):
        cnt = 0
        for a in A:
            # X未満の個数
            idx = bisect_left(A, x - a)
            # X以上の個数
            cnt += N - idx
        # X以上を使う！と決めた時、M個以上になるか
        return cnt >= M

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))

    ng = 10 ** 18
    ok = 0
    # X以上を使う！と決めるとX以上の個数が自明にわかる。
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if getCount(mid):
            ok = mid
        else:
            ng = mid

    # M個以上あることがわかれば、Mよりも余分な数(同じ値が複数ある場合)
    # はすべてXである事がわかるため、差分だけ引けば良い。
    B = [0] + list(accumulate(A))
    ans = 0
    cnt = 0
    for i in range(N):
        idx = bisect_left(A, ok - A[i])
        ans += B[N] - B[idx] + A[i] * (N - idx)
        cnt += N - idx

    rest = (cnt - M) * ok
    print(ans - rest)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines  

import numpy as np

def shake_cnt(x):
  # 両手x - 左手の価値 = 右手の価値
  # x - a[i]未満の個数(行わない握手)を数える
  # X以上の和がM個未満かどうか
  X = np.searchsorted(A, x-A)
  return (N - X).sum()
  

N, M = map(int, input().split())
A = np.array(input().split(),np.int64)
A.sort()

left = 0 # 握手の回数がM以上
right = 10 ** 6 # 握手の回数がM未満
while left + 1 < right:
    x = (left + right) // 2
    if shake_cnt(x) < M:
        right = x
    else:
        left = x

# 終了時にngにX-1,okにXが入っている。

X = np.searchsorted(A,right-A) # 行わない人数
Acum = np.zeros(N+1,np.int64) # 人数 -> 累積和
Acum[1:] = np.cumsum(A)

# right(最大値) 以上の握手を全て行ったとして、回数と総和を計算
# N**2通りの握手から価値の高い上位の握手  

shake = N * N - X.sum() # 総数-行わない人数
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()
happy += (M - shake) *left
print(happy)
### BUGGY CODE ###

from collections import deque

n,m,k = map(int,input().split())
ans = [[0]*n for i in range(n)]

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

group = [-1]*n
def check():
    
    count = 1
    for i in range(n):
        if group[i] == -1:
            dfs(i,count)
            count += 1
    return group

def dfs(i,count):
    q = deque([])
    q.append(i)
    while q:
        bef = q.pop()

        for nex in fre[bef]:
            if group[nex] == -1:
                group[nex] = count
                q.append(nex)
    
check()
for i in range(n):
    if group[i] == -1:
        print(0,end=" ")
    else:
        num = group.count(group[i])
        num -= len(fre[i])
        for j in blo[i]:
            if group[j] == group[i]:
                num -= 1
        print(num-1,end=" ")






### FIXED CODE ###

def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

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

    fre = [[] for i in range(n)]

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

    group = [-1]*n
    def check():
        dic = {}
        count = 1
        for i in range(n):
            if group[i] == -1:
                a = dfs(i,count)
                dic[count] = a
                count += 1
        return group,dic

    def dfs(i,count):
        num = 0
        group[i] = count
        q = deque([])
        q.append(i)
        while q:
            bef = q.pop()

            for nex in fre[bef]:
                if group[nex] == -1:
                    group[nex] = count
                    q.append(nex)
                    num += 1
        return num
    group,dic = check()
    ans = []
    for i in range(n):
        a = group[i]
        ans.append([dic[a]-len(fre[i]),a])
    for i in range(k):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        if ans[a][1] == ans[b][1]:
            ans[a][0] -= 1
            ans[b][0] -= 1
    for i,j in ans:
        print(i,end=" ")

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

n = int(input())

ans = 1
for i in range(1,n+1):
    ans *= i
print(ans%1000000007)

### FIXED CODE ###

n = int(input())

ans = 1
for i in range(1,n+1):
    ans *= i
    ans = ans%1000000007 
print(ans)
### BUGGY CODE ###

N = int(input())
A = []

for i in range(N):
    tmp = int(input())
    A.append(tmp)

for i in range(N):
    tA = A.copy()
    # print(tA)
    tA.pop(i)
    print(max(tA))

### FIXED CODE ###

N = int(input())
A = []

for i in range(N):
    tmp = int(input())
    A.append(tmp)

As = ld = sorted(A, reverse=True)
# print(As)
m = As[0:2]
# print(m)
for i in range(N):
    if A[i] == m[0]:
        print(m[1])
    else:
        print(m[0])
### BUGGY CODE ###

import math
import bisect

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

for i in range(M):
    n = A.pop() / 2
    bisect.insort(A, n)

print(sum(math.floor(A[j]) for j in range(N)))

### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_minus = [-x for x in A]
heapify(A_minus)

for i in range(M):
    n = -heappop(A_minus) // 2
    heappush(A_minus, -n)

print(-sum(A_minus))
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,K = list(map(int, input().split()))
# h = list(map(int, input().split()))
(N,K), h = map(int, input().split()), list(map(int, input().split()))

# suml = [1e9 for i in range(N)]
# suml[0] = 0
suml = [0]*N

for e in range(1,N):

    # for k in range(1, min([e, K])+1):
    #     suml[e] = min(suml[e],
    #             abs(h[e]-h[e-k]) + suml[e-k]
    #     )
    start = max(0, e-K)
    cost  = min(cst + abs( h[e] - hgh ) for cst, hgh in zip(suml[start:e], 
           h[start:e]))
    suml[e] = cost

print(suml[N-1])
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# N,K = list(map(int, input().split()))
# h = list(map(int, input().split()))

# (N,K), h = map(int, input().split()), list(map(int, input().split()))
N,K,*h = map(int, "\n".join([input(), input()]).split())

# suml = [1e9 for i in range(N)]
# suml[0] = 0


suml = [0]*N

# for i in range(1,N):
for i,e_h in enumerate(h):
    if i == 0:
        continue

    start = max(0, i-K)
    cost  = min(cst + abs( e_h - hgh) for cst, hgh in 
                   zip(suml[start:i], h[start:i]))
    # cost  = min(cst + abs( h[i] - hgh ) for cst, hgh in 
    #               zip(suml[start:i], h[start:i]))
    suml[i] = cost

print(suml[-1])
### BUGGY CODE ###

import sys
import fractions, math
from functools import reduce

def gcd(i, j, k):
    return fractions.gcd(i, fractions.gcd(j, k))

def solve(K: int):
    counter = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                counter += gcd(i, j, k)
    print(counter)
    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()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import fractions, math
from functools import reduce

def solve(K: int):
    counter = 0
    L = [0] * 201
    for i in range(1, K+1):
        for j in range(1, K+1):
            L[math.gcd(i, j)] += 1
    for i in range(1, K+1):
        for j in range(1, K+1):
            counter += math.gcd(i, j) * L[j]
    print(counter)
    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()
    K = int(next(tokens))  # type: int
    solve(K)

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

import queue

N = int(input())
E = {n: set() for n in range(N)}

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].add((b, c))
    E[b].add((a, c))

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
que.put((K, 0))
while not que.empty():
    now, d = que.get()
    already.add(now)
    dist[now] = d
    out = E[now]
    for n, c in out:
        if n in already:
            continue
        que.put((n, d + c))

for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(dist[x] + dist[y])


### FIXED CODE ###

import queue

N = int(input())
E = {n: set() for n in range(N)}

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].add((b, c))
    E[b].add((a, c))

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
que.put((K, 0))
while not que.empty():
    now, d = que.get()
    already.add(now)
    dist[now] = d
    out = E[now]
    for n, c in out:
        if n in already:
            continue
        que.put((n, d + c))

for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(dist[x] + dist[y])
### BUGGY CODE ###

from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import Counter
from pprint import pprint

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

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    elif s[i]=="B":
        b.append(i)
    else:
        pass
# print(r,g,b)
count = 0
for i in r:
    for j in g:
        # print(i,j)
        if i<j:
            x = i
            y = j
        else:
            x = j
            y = i
        k1 = y + (y - x)
        if k1 in b:    
            count += 1
        k2 = x - (y - x)
        if k2 in b:
            count += 1
        k3 = (x+y)/2
        if k3 in b:
            count += 1
# print(len(r) * len(g) * len(b))
# print(count)
ans = len(r) * len(g) * len(b) - count
print(ans)

### FIXED CODE ###

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    elif s[i]=="B":
        b.append(i)
    else:
        pass
# print(r,g,b)
count = 0
for i in range(n):
    x = s[i]
    for sa in range(n):
        j = i + sa
        k = j + sa
        if j<n:
            y = s[j]
        else:
            break
        if k<n:
            z = s[k]
        else:
            break
        if x!=y and y!=z and z!=x:
            count += 1
# print(count)
ans = len(r) * len(g) * len(b) - count
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
ans = 0
while True:
    i = S.find('ABC')
    if i == -1:
        break
    elif i == 0:
        S = 'BCA' + S[i+3:]
        ans += 1
    elif i == N-3:
        S = S[:i]+'BCA'
        ans += 1
    else:
        S = S[:i]+'BCA'+S[i+3:]
        ans += 1
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)

if S[0] == 'A':
    ac = 1
else:
    ac = 0

ans = 0
for i in range(1,N):
    if S[i] == 'A':
        if S[i-1] != 'A':
            ac = 1
        else:
            ac += 1
    elif S[i] == 'B':
        if S[i-1] != 'A':
            ac = 0
    else:
        if S[i-1] == 'B':
            ans += ac
            S[i] = 'A'
        else:
            ac = 0

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, Q = map(int, input().split())
    S = input()
    for _ in range(Q):
        l, r = map(int, input().split())
        cnt = 0
        s = S[l - 1:r]
        for i in range(r - l):
            if s[i:i + 2] == "AC":
                cnt += 1
        print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, Q = map(int, input().split())
    S = input()

    ac_count = [0]
    ac = 0
    for i in range(1, N):
        if S[i - 1:i + 1] == "AC":
            ac += 1
        ac_count.append(ac)

    result = []

    for _ in range(Q):
        left, right = map(int, input().split())
        result.append(ac_count[right - 1] - ac_count[left - 1])

    print(*result, sep="\n")


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

N = int(input())
S=[]
for n in range(N):
    S.append(input())
def isAna(a,b):
    boolcount = True
    listb = list(b)
    for ai in list(a):
        if ai in listb:
            listb.remove(ai)
        else:
            boolcount = False
            break
    return boolcount
count = 0
for i,s in enumerate(S):
    for ss in S[i+1:]:
        if isAna(s,ss) == True:
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
S=[]
for n in range(N):
    S.append(input())
Sdict = {}
for s in S:
    lists = list(s)
    listss = sorted(lists)
    listsss = ''.join(listss)
    if Sdict.get(listsss) == None:
        Sdict[listsss] = 1
    else:
        Sdict[listsss] += 1
count = 0
for value in Sdict.values():
    count += int(value*(value-1)/2)
print(count)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

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

ans = 0
for i in range(N):
    new_list = A[:i] + A[i+1:]
    ans = max(ans, gcd_list(new_list))

print(ans)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

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

gcd_front = gcd(A[0], A[1])
gcd_front_list = [A[0],gcd_front, ]
for i in range(2, N):
    gcd_front = gcd(gcd_front, A[i])
    gcd_front_list.append(gcd_front)

gcd_rear = gcd(A[N-1], A[N-2])
gcd_rear_list = [A[N-1], gcd_rear, ]

for i in range(N-3, -1, -1):
    gcd_rear = gcd(gcd_rear, A[i])
    gcd_rear_list.append(gcd_rear)

ans = 0

for i in range(N):
    if i == 0:
        ans = max(ans, gcd_rear_list[-2])
    if i == N-1:
        ans = max(ans, gcd_front_list[-2])   

    ans = max(ans, gcd(gcd_front_list[i-1],gcd_rear_list[N-2-i]))
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

def main():
  n = int(input())
  tree = defaultdict(lambda : {'parent':-1, 'score':0, 'children':[]})
  weights = dict()
  for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a]['children'].append(b)
    tree[b]['children'].append(a)
    weights[(a, b)] = weights[(b, a)] = c
    
  q, k = map(int, input().split())  
  visited = [False] * (n+1)
  iroot = k
  def dfs(inode, score=0):
    visited[inode] = True
    for ichild in tree[inode]['children']:
      if visited[ichild]:
        continue
      tree[ichild]['score'] = weights[(inode, ichild)] + score
      tree[ichild]['parent'] = inode
      dfs(ichild, tree[ichild]['score'])
  dfs(iroot)
  for _ in range(q):
    x, y = map(int, input().split())
    print(tree[x]['score'] + tree[y]['score'])

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import sys
sys.setrecursionlimit(10**9)

def main():
  n = int(input())
  inode2scores = [0] * (n+1)
  tree = [[] for _ in range(n+1)]
  weights = dict()
  for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    weights[(a, b)] = weights[(b, a)] = c
    
  q, k = map(int, input().split())  
  visited = [False] * (n+1)
  iroot = k
  def dfs(inode, score=0):
    visited[inode] = True
    for ichild in tree[inode]:
      if visited[ichild]:
        continue
      inode2scores[ichild] = weights[(inode, ichild)] + score
      dfs(ichild, inode2scores[ichild])
  dfs(iroot)
  for _ in range(q):
    x, y = map(int, input().split())
    print(inode2scores[x] + inode2scores[y])

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

import re
n, q = [int(i) for i in input().split()]
S = input()
for _ in range(q):
    l, r = [int(i) for i in input().split()]
    s = S[l-1:r]
    ans = sum(True for _ in re.finditer('AC', s))
    print(ans)

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
S = input()
counter = [0] * len(S)
for i in range(len(S)):
    if i == 0:
        counter[i] == 0
    elif S[i-1:i+1] == 'AC':
        counter[i] = counter[i-1] + 1
    else:
        counter[i] = counter[i-1]

counter = [0] + counter
# print(counter)


for _ in range(q):
    l, r = [int(i) for i in input().split()]
    print(counter[r] - counter[l])
### BUGGY CODE ###

S = input()

S = [s for s in S]

out = [0] * len(S)

for i, n in enumerate(S):
    if n == 'R':
        found = False
        cnt = 1

        while not found:
            if S[i + cnt] == 'L':
                found = True
            else:
                cnt += 1

        if cnt % 2 == 0:
            out[i + cnt] += 1
        else:
            out[i + cnt - 1] += 1

    else:
        found = False
        cnt = 1

        while not found:
            if S[i - cnt] == 'R':
                found = True
            else:
                cnt += 1

        if cnt % 2 == 0:
            out[i - cnt] += 1
        else:
            out[i - cnt + 1] += 1


out1 = [str(n) for n in out]

print(' '.join(out1))

### FIXED CODE ###

S = input()
S = [s for s in S]

out = [0] * len(S)

if S[0] == 'R':
    top_R = True
    top_L = False
else:
    top_R = False
    top_L = True

for i, n in enumerate(S):
    if n == 'R':
        if top_R:
            found = False
            cnt = 1
            while not found:
                if S[i + cnt] == 'L':
                    found = True
                else:
                    cnt += 1
            top_R = False
        else:
            cnt -= 1

        if cnt % 2 == 0:
            out[i + cnt] += 1
        else:
            out[i + cnt - 1] += 1

        if cnt != 1:
            top_R = False
        else:
            top_L = True
    else:
        if top_L:
            found = False
            cnt = 1
            while not found:
                if S[i - cnt] == 'R':
                    found = True
                else:
                    cnt += 1
            top_L = False
        else:
            cnt += 1

        if cnt % 2 == 0:
            out[i - cnt] += 1
        else:
            out[i - cnt + 1] += 1

        if cnt != 1:
            top_L = False
        else:
            top_R = True

out1 = [str(n) for n in out]
print(' '.join(out1))