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

from collections import Counter
N = int(input())
S = input()
tmp = Counter(S)
# print(tmp)
r = tmp["R"]
g = tmp["G"]
b = tmp["B"]
ans = 0
# for s in S:
#     if s == "R":
#         r += 1
#     elif s == "G":
#         g += 1
#     else:
#         b += 1

for i in range(len(S) - 2):
    j = 1
    if S[i] == "R":
        ans += g * b
        r -= 1
    elif S[i] == "G":
        ans += r * b
        g -= 1
    else:
        ans += r * g
        b -= 1
    
    while not (i + j + j >= len(S)):
        if S[i] == "R":
            if S[i + j] == "R" or S[i + j+j] == "R":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "G":
                ans -= 1
        if S[i] == "G":
            if S[i + j] == "G" or S[i + j+j] == "G":
                j += 1
                continue
            if S[i + j] == "R" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "R":
                ans -= 1
        if S[i] == "B":
            if S[i + j] == "B" or S[i + j+j] == "B":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "R" or S[i + j] == "R" and S[i + j + j] == "G":
                ans -= 1
        j += 1
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
tmp = Counter(S)
# print(tmp)
r = tmp["R"]
g = tmp["G"]
b = tmp["B"]
ans = 0
# for s in S:
#     if s == "R":
#         r += 1
#     elif s == "G":
#         g += 1
#     else:
#         b += 1

for i in range(len(S) - 2):
    j = 1
    if S[i] == "R":
        ans += g * b
        r -= 1
    elif S[i] == "G":
        ans += r * b
        g -= 1
    else:
        ans += r * g
        b -= 1
    
    while not (i + j + j >= len(S)):
        if S[i] == "R":
            if S[i + j] == "R":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "G":
                ans -= 1
        if S[i] == "G":
            if S[i + j] == "G":
                j += 1
                continue
            if S[i + j] == "R" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "R":
                ans -= 1
        if S[i] == "B":
            if S[i + j] == "B":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "R" or S[i + j] == "R" and S[i + j + j] == "G":
                ans -= 1
        j += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a_list = [int(num) for num in input().split(" ")]

total_comb = 0
ball_num_count = {}
for i in range(1,n+1):
    i_count = a_list.count(i)
    total_comb += int(i_count*(i_count-1)/2)
    ball_num_count[i] = i_count-1
for k in range(n):
    except_num = a_list[k]
    print(total_comb - ball_num_count[except_num])


### FIXED CODE ###

import collections

n = int(input())
a_list = [int(num) for num in input().split(" ")]
c_dict = collections.Counter(a_list)

total_comb = 0
for i in c_dict:
    i_count = c_dict[i]
    total_comb += int(i_count*(i_count-1)/2)
for k in range(n):
    except_num = a_list[k]
    print(total_comb - (c_dict[except_num]-1))
### BUGGY CODE ###

k = int(input())
import fractions
l = []
ans = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b,k+1):
            l = [a,b,c]
            d = l[0]
            for i in range(1,3):
                d = fractions.gcd(d,l[i])
            if a != b and b!= c and a!= c:
                ans+= d*6
            elif (a==b and a!=c) or (a==c and a!= b) or (b == c and a!= b):
                ans+= d*3
            else:
                ans+= d
print(ans)            


### FIXED CODE ###

k = int(input())
import math
l = []
ans = 0
e = 0
d = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        e = math.gcd(a,b)
        for c in range(b,k+1):
            d = math.gcd(e,c)
            if a != b and b!= c and a!= c:
                ans+= d*6
            elif (a==b and a!=c) or (a==c and a!= b) or (b == c and a!= b):
                ans+= d*3
            else:
                ans+= d
print(ans)
### BUGGY CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    g = gcd(A[0],A[1])
    lcm = (A[0]*A[1]) // g
    for x in A[2:]:
        if max(lcm,x) % min(lcm,x) == 0:
            g = min(lcm,x)
        else:
            g = gcd(lcm,x)
        lcm = (lcm * x) // g
    ans = 0
    for x in A:
        ans = (ans + (lcm // x)) % 1000000007
    print(ans)

### FIXED CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    g = gcd(A[0],A[1])
    lcm = (A[0]*A[1]) // g
    for x in A[2:]:
        lcm = (lcm * x) // gcd(lcm,x)
    print(sum((lcm//x) for x in A)%1000000007)
### BUGGY CODE ###

H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  print(sum(dp[L:R:D]))

### FIXED CODE ###

H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i]=dpsum[i-D]+dp[i]
  else:
    dpsum[i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R-D]-dpsum[L-D])
  else:
    print(dpsum[R-D])
### BUGGY CODE ###

n, x, y = map(int, input().split())

inf = 1000000000
edges = [[inf] * n for _ in range(n)]
for i in range(n - 1):
    edges[i][i + 1] = 1
    edges[i + 1][i] = 1

edges[x - 1][y - 1] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])

cnts = [0] * (n - 1)
for i in range(n - 1):
    for j in range(i + 1, n):
        cnts[edges[i][j] - 1] += 1

for x in cnts:
    print(x)


### FIXED CODE ###

n, x, y = map(int, input().split())

ans = [0] * n
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        ans[min(j - i, min(abs(i - x) + 1 + abs(y - j),
                           abs(i - y) + 1 + abs(x - j)))] += 1

for x in ans[1:]:
    print(x)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
tmp = 0
key = 0
for i in range(n):
    if tmp + a[i] >= sum(a) / 2:
        key = i
        break
    tmp += a[i]

ans = abs(sum(a[0:key]) - sum(a[key::]))
tmp = 0
key = 0
for i in range(n):
    tmp += a[i]
    if tmp >= sum(a) / 2:
        key = i + 1
        break

ans = min(abs(sum(a[0:key]) - sum(a[key::])), ans)
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
tmp = 0
key = 0
SUMA = sum(a)

for i in range(n):
    if tmp + a[i] >= SUMA / 2:
        key = i
        break
    tmp += a[i]

ans = abs(sum(a[0:key]) - sum(a[key::]))
tmp = 0
key += 1
ans = min(abs(sum(a[0:key]) - sum(a[key::])), ans)
print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline

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

BC = [tuple(map(int, input().split())) for _ in range(m)]

for b, c in BC:
    for _ in range(b):
        A.append(c)

A = list(map(lambda x: -x, A))
heapify(A)

answer = 0
for _ in range(n):
    answer += heappop(A)

print(-answer)


### FIXED CODE ###

from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline

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

BC = [tuple(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: x[1], reverse=True)

for i in range(m):
    for _ in range(BC[i][0]):
        min_num = heappop(A)
        if min_num < BC[i][1]:
            heappush(A, BC[i][1])
        else:
            heappush(A, min_num)
            break

total = sum(A)
print(total)
### BUGGY CODE ###

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

import numpy as np

N, K = map(int, input().split())
 
h = np.array(list(map(int, input().split())))
 
dp = np.full(N, np.inf)
dp[0] = 0
 
for n in range(1, N):
    k = min(K, n)
    temp = np.min(dp[n-k:n] + np.abs(h[n]-h[n-k:n]))
    dp[n] = temp
print(int(dp[-1]))

### FIXED CODE ###

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

import numpy as np

N, K = map(int, input().split())
 
h = np.array(list(map(int, input().split())))
 
dp = np.zeros(N)
 
for n in range(1, N):
    k = min(K, n)
    temp = np.min(dp[n-k:n] + np.abs(h[n]-h[n-k:n]))
    dp[n] = temp
print(int(dp[-1]))
### BUGGY CODE ###

S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]
#print(dp[0])
for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  #print(dp[i+1])
  dp.append(dpn)
print(dp[len(S)][5])


### FIXED CODE ###

S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]
#print(dp[0])
for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  #print(dp[i+1])
  dp.append(dpn)
print(dp[len(S)][5])
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        fix = [0] + a[0:i] + a[i + 1:n] + [0]
        ans[i] = sum([abs(fix[j] - fix[j - 1]) for j in range(1, n + 1)])
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n = int(input())
    a = [0] + list(map(int, input().split())) + [0]
    dist = [abs(a[i] - a[i - 1]) for i in range(1, n + 2)]
    total = sum(dist)
    ans = [0] * n
    for i in range(n):
        ans[i] = total - dist[i] - dist[i + 1] + abs(a[i] - a[i + 2])
    print(*ans, sep='\n')


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

import time
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()
    now=time.time()
    if (now-start)>1.8:
        print(m)
        exit()

### FIXED CODE ###

import time
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()
    now=time.time()
    if (now-start)>1.6:
        print(m)
        exit()
### BUGGY CODE ###

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

cnt = 0

if k % 2 == 0:
  k_2 = k // 2
else:
  k_2 = k

for a in range(k_2, n+1, k_2):
  for b in range(k-(a%k), n+1, k):
    for c in range(k-(a%k), n+1, k):
      cnt += 1
        
print(cnt)


### FIXED CODE ###

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

cnt = 0

if k % 2 == 0:
  k_2 = k // 2
else:
  k_2 = k

for a in range(k_2, n+1, k_2):
  cnt += len(range(k-(a%k), n+1, k)) ** 2
        
print(cnt)
### BUGGY CODE ###

def main():
  s = input()
  q = int(input())
  c = [[i for i in input().split()] for j in range(q)]

  for i in c:
    if i[0] == '1':
      s = s[::-1]
    else:
      if i[1] == '1':
        s = i[2] + s
      else:
        s = s + i[2]
  print(s)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from collections import deque
  s = list(input())
  s = s[:-1]
  s = deque(s)
  q = int(input())
  c = [[i for i in input().split()] for j in range(q)]
  cnt = 1
  for i in c:
    if i[0] == '1':
      cnt *= -1
    else:
      if (i[1] == '1' and cnt == 1) or (i[1] == '2' and cnt == -1):
        s.appendleft(i[2])
      else:
        s.append(i[2])
  if cnt == 1:
    print(''.join(s))
  else:
    print(''.join(s)[::-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import math

n = int(sys.stdin.readline().strip())

a = math.ceil(math.sqrt(n))
for i in range(a, n+1):
    if n % i == 0:
        m1 = i
        m2 = int(n/i)
        break
    else:
        continue

ord1 = int(math.log10(m1) + 1)
ord2 = int(math.log10(m1) + 1)
ans = max(ord1, ord2)
print(ans)


### FIXED CODE ###

import sys
import math

n = int(sys.stdin.readline().strip())

a = math.ceil(math.sqrt(n))

ans = 10
i = a
while i > 0:
    if n % i == 0:
        m1 = i
        m2 = int(n/i)

        m = max(m1, m2)
        ord_m = int(math.log10(m) + 1)
        ans = min(ans, ord_m)
    i -= 1

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

N=int(input())
member=["0"]+input().split()
answer=""
for i,x in enumerate(member):
    answer=answer+str(member.count(str(i+1)))+"\n"
print(answer[:-1])


### FIXED CODE ###

a=[0]*int(input())
for i in input().split():a[int(i)-1]+=1
print(*a)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
for i in range(k):
    a=h.index(max(h))
    h[a]=0
print(sum(h))


### FIXED CODE ###

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

if k<n:
    print(sum(h[:n-k]))
else:
    print(0)
### BUGGY CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,ls,c):
    l=ls-1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l-ls+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            ans += bin_search(arr,j+1,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------


### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,ls,c):
    l=ls-1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l-ls+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            ans += bin_search(arr,j+1,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

def p_d():
    from collections import defaultdict
    from heapq import heappush, heappop
    N, K = map(int, input().split())
    li = []
    for _ in range(N):
        t, d = map(int, input().split())
        li.append((t, d))
    li.sort(key=lambda x: x[1], reverse=True)
    sushi = defaultdict(list)
    ans = 0
    for i in range(K):
        heappush(sushi[li[i][0]], li[i][1])
        ans += li[i][1]
    ans += len(sushi.keys()) ** 2

    ans_list = [ans]
    while True:
        k, v = -1, 10 ** 9 + 1
        for key in sushi.keys():
            if len(sushi[key]) > 1:
                tmp = heappop(sushi[key])
                if v > tmp:
                    if k != -1:
                        heappush(sushi[k], v)
                    k, v = key, tmp
                else:
                    heappush(sushi[key], tmp)
        if k == -1:
            break
        while K < N and li[K][0] in sushi.keys():
            K += 1
        if K == N:
            break
        ans -= v
        ans -= len(sushi.keys()) ** 2
        heappush(sushi[li[K][0]], li[K][1])
        ans += li[K][1]
        ans += len(sushi.keys()) ** 2
        ans_list.append(ans)
    print(max(ans_list))


if __name__ == '__main__':
    p_d()


### FIXED CODE ###

def p_d():
    N, K = map(int, input().split())
    inf = 10 ** 18
    sushi = [[-inf] for _ in range(N)]
    max_kind = -1
    for _ in range(N):
        t, d = map(int, input().split())
        sushi[t - 1].append(d)
        if max_kind < t:
            max_kind = t
    for i in range(max_kind):
        sushi[i].sort(reverse=True)
    sushi.sort(key=lambda x: x[0], reverse=True)

    que = []
    res = 0
    for i in range(K):
        res += sushi[i][0]
        for j in sushi[i][1:]:
            que.append(j)
    que.sort()
    cur = res
    res += K ** 2
    for var in range(1, K)[::-1]:
        a = que.pop()
        b = sushi[var][0]
        cur += a - b
        res = max(res, cur + var ** 2)
    print(res)


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

from bisect import bisect_left as bl, bisect_right as br
from collections import deque
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

S = sorted(A)
D = {a: i for i, a in enumerate(S)}

BB = [0] * (N+1)
for i in range(N):
    BB[D[A[i]] + 1] = B[i]

for i in range(1, N+1):
    BB[i-1] ^= BB[i]

A = [D[a] for a in A]
X = [[] for _ in range(N+1)]
DD = {}
for i in range(M):
    l, r = map(int, input().split())
    l = bl(S, l)
    r = bl(S, r+1)
    X[l].append(r)
    X[r].append(l)
    DD[(l<<18) + r] = i
    DD[(r<<18) + l] = i

Q = deque([i for i in range(N+1)])
P = [-1] * (N+1)
CH = [[] for _ in range(N+1)]
R = []
done = [0] * (N+1)
while Q:
    i = deque.pop(Q)
    if P[i] < 0: R.append(i)
    for j in X[i]:
        if P[j] >= 0: continue
        if j != P[i]:
            R.append(j)
            P[j] = i
            CH[i].append(j)
            deque.append(Q, j)

ANS = []
for i in R[1:][::-1]:
    if BB[i]:
        BB[i] ^= 1
        BB[P[i]] ^= 1
        if P[i] < 0:
            print(-1)
            exit()
        ANS.append(DD[(i<<18) + P[i]] + 1)
if sum(BB) == 0:
    print(len(ANS))
    print(*sorted(ANS))
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# from bisect import bisect_left as bl, bisect_right as br
# from collections import deque
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

S = sorted(A)
D = {a: i for i, a in enumerate(S)}

BB = [0] * (N+1)
for i in range(N):
    BB[D[A[i]] + 1] = B[i]

for i in range(1, N+1):
    BB[i-1] ^= BB[i]

def bl(L, k):
    l, r = -1, len(L)
    while r - l > 1:
        m = (l+r) // 2
        if L[m] >= k:
            r = m
        else:
            l = m
    return r

A = [D[a] for a in A]
X = [[] for _ in range(N+1)]
DD = {}
for i in range(M):
    l, r = map(int, input().split())
    l = bl(S, l)
    r = bl(S, r+1)
    X[l].append(r)
    X[r].append(l)
    DD[(l<<18) + r] = i
    DD[(r<<18) + l] = i

# Q = deque([i for i in range(N+1)])
# Q = [i for i in range(N+1)]
P = [-1] * (N+1)
CH = [[] for _ in range(N+1)]
R = []
done = [0] * (N+1)
for ii in range(N+1):
    Q = [ii]
    while Q:
        i = Q.pop()
        if P[i] < 0:
            R.append(i)
            done[i] = 1
        for j in X[i]:
            if P[j] >= 0: continue
            if j != P[i] and done[j] == 0:
                R.append(j)
                done[j] = 1
                P[j] = i
                CH[i].append(j)
                # X[j].remove(i)
                # deque.append(Q, j)
                Q.append(j)

ANS = []
for i in R[1:][::-1]:
    if BB[i]:
        BB[i] ^= 1
        BB[P[i]] ^= 1
        if P[i] < 0:
            print(-1)
            exit()
        ANS.append(DD[(i<<18) + P[i]] + 1)
if sum(BB) == 0:
    print(len(ANS))
    print(*sorted(ANS))
else:
    print(-1)
### BUGGY CODE ###

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

def count_DMC(k):
  num_d = [0] * (N+1)
  num_m = [0] * (N+1)
  num_dm = [0] * (N+1)
  res = 0
  for i, s in enumerate(S, 1):
    num_d[i] += num_d[i-1]
    num_m[i] += num_m[i-1]
    num_dm[i] += num_dm[i-1]
    if i - k - 1 >= 0 and S[i-k-1]=='D':
      num_dm[i] -= num_m[i]
    if s == 'D':
      num_d[i] += 1
      if i + k <= N:
        num_d[i+k] -= 1
    if s == 'M':
      num_m[i] += 1
      if i + k <= N:
        num_m[i+k] -= 1
      num_dm[i] += num_d[i]
    if s == 'C':
      res += num_dm[i]
  return res

for k in K:
  print(count_DMC(k))


### FIXED CODE ###

import numpy as np

N = int(input())
S = np.array(list(input()))
Q = int(input())
K = list(map(int, input().split()))


D_idx = S == 'D'
M_idx = S == 'M'
C_idx = S == 'C'

num_d = D_idx.cumsum(dtype=int)
num_m = M_idx.cumsum(dtype=int)

def count_DMC(k):
  _num_d = num_d.copy()
  _num_d[k:] = _num_d[k:] - _num_d[:-k] # k個先になったらカウントを減らす
  _num_m = num_m.copy()
  _num_m[k:] = _num_m[k:] - _num_m[:-k] # 同上
  num_dm = _num_d * M_idx # 'M'の位置における'DM'の個数
  num_dm[k:] -= D_idx[:-k] * _num_m[k-1:-1]
  return (num_dm.cumsum(dtype=int) * C_idx).sum()


for k in K:
  print(count_DMC(k))
### BUGGY CODE ###

N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
for num in teiki_1:
    if num in teiki_N:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')


### FIXED CODE ###

N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
if len(set(teiki_1) & set(teiki_N)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

n= int(input())
s = {}

for i in range(n):
    t = input()
    s.setdefault(t, 1)
    s[t] += 1

max_k_list = [kv[0] for kv in s.items() if kv[1] == max(s.values())]

max_k_list.sort()

for i in range(len(max_k_list)):
    print(max_k_list[i])

### FIXED CODE ###

n= int(input())
s = {}

for _ in range(n):
    t = input()
    s.setdefault(t, 1)
    s[t] += 1

ans = []
m = max(s.values())
for k, v in s.items():
    if v == m:
        ans.append(k)

for m in sorted(ans):
    print(m)