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

n = int(input())
p = [list(map(int,input().split())) for _ in range(n)]

X = sorted([(i, xy[0]) for i, xy in enumerate(p)], key=lambda x: x[1])
Y = sorted([(i, xy[1]) for i, xy in enumerate(p)], key=lambda x: x[1])
dX = [[X[i][0], X[i+1][0], X[i+1][1]-X[i][1]] for i in range(n-1)]
dY = [[Y[i][0], Y[i+1][0], Y[i+1][1]-Y[i][1]] for i in range(n-1)]
D = sorted(dX+dY, key=lambda x: x[2])

def root(x):
    if parent[x] == x:
        return x
    else:
        return root(parent[x])

def connected(x, y):
    return root(x) == root(y)

parent = [i for i in range(n+1)]
ans = 0

while D:
    a, b, d = D.pop(0)
    if not connected(a, b):
        parent[root(b)] = root(a)
        ans += d
print(ans)


### FIXED CODE ###

n = int(input())
p = [list(map(int,input().split())) for _ in range(n)]

X = sorted([(i, xy[0]) for i, xy in enumerate(p)], key=lambda x: x[1])
Y = sorted([(i, xy[1]) for i, xy in enumerate(p)], key=lambda x: x[1])
dX = sorted([[X[i][0], X[i+1][0], X[i+1][1]-X[i][1]] for i in range(n-1)], key=lambda x: x[2])
dY = sorted([[Y[i][0], Y[i+1][0], Y[i+1][1]-Y[i][1]] for i in range(n-1)], key=lambda x: x[2])

def root(x):
    if parent[x] == x:
        return x
    else:
        return root(parent[x])

def connected(x, y):
    return root(x) == root(y)

parent = [i for i in range(n+1)]
depth = [1 for i in range(n+1)]

ans = 0
i, j = 0, 0
while i < n-1 and j < n-1:
    if dX[i][2] < dY[j][2]:
        a, b, d = dX[i]
        i += 1
    else:
        a, b, d = dY[j]
        j += 1
    ra, rb = map(root, [a,b])
    if ra != rb:
        if depth[ra] < depth[rb]:
            a, b = b, a
            ra, rb = rb, ra
        parent[rb] = ra
        depth[ra] = max(depth[ra], depth[rb]+1)
        ans += d
print(ans)
### BUGGY CODE ###

def main():
    # initialize
    N = int(input())
    nums = [int(n) for n in input().split(' ')]

    hash_table = {}
    for n in nums:
        if n in hash_table.keys():
            hash_table[n] += 1
        else:
            hash_table[n] = 1

    for n in nums:
        ans = 0
        for k, v in hash_table.items():
            if k == n:
                v -= 1
            ans += v * (v - 1) / 2 if v > 1 else 0
        print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    # initialize
    _ = int(input())
    nums = [int(n) for n in input().split(' ')]

    hash_table = {}
    for n in nums:
        if n in hash_table.keys():
            hash_table[n] += 1
        else:
            hash_table[n] = 1

    ans_cash = {}
    for n in nums:
        num_n = hash_table[n]
        if num_n in ans_cash.keys():
            ans = ans_cash[num_n]
        else:
            ans = 0
            for k, v in hash_table.items():
                if k == n:
                    v -= 1
                ans += v * (v - 1) / 2 if v > 1 else 0
            ans_cash[num_n] = ans
        print(int(ans))


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

def main():
    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    for m in range(0, M):
        tmp = [int(x) for x in input().split()]
        A.extend([tmp[1]] * tmp[0])

    A.sort()
    A.reverse()
    A = A[:N]
    print(sum(A))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappush, heappop, heapify

def main():
    N, M = map(int, input().split())
    A_card = [-int(x) for x in input().split()]

    change_list = []
    for i in range(M):
        B, C = [int(x) for x in input().split()]
        change_list.append(((-1) * C, B))

    hq = []
    for i in range(N):
        heappush(hq, (A_card[i], 1))

    for i in range(M):
        heappush(hq, change_list[i])

    result_sum = 0
    count = 0
    while True:
        if count == N:
            break
        tmp = heappop(hq)
        if count + tmp[1] <= N:
            result_sum += (tmp[0] * tmp[1])
            count += tmp[1]
        else:
            result_sum += (tmp[0] * (N - count))
            break

    print(result_sum * (-1))

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

import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
cost = [[None] * (n + 1) for j in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    cost[u][v] = w
    cost[v][u] = w
ans = [] * (n + 1)


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if dist[w] == -1:
                dist[w] = dist[v] + cost[w][v]
                dist[w] %= 2
                stack.append(w)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")


### FIXED CODE ###

import sys

input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))


def dfs(a):
    dist = [-1] * (n + 1)
    stack = [a]
    dist[a] = 0
    while stack:
        v = stack.pop()
        for b, w in graph[v]:
            if dist[b] == -1:
                dist[b] = (dist[v] + w) % 2
                stack.append(b)
            else:
                continue
    return dist


dist = dfs(1)
print(*dist[1:], sep="\n")
### BUGGY CODE ###

K = int(input())
dicts = {}
for _ in range(K):
    string = str(sorted(input()))
    if string in dicts:
        dicts[string] += 1
    else:
        dicts[string] = 1
# print(dicts)

def calc_pairs(n):
    return n*(n-1)//2
answer = 0
for i,v in dicts.items():
    answer += calc_pairs(v)
    
# answer = 0
# for i in range(K-1):
#     for j in range(i+1,K):
#         if strs[i] == strs[j]:
#             answer += 1

print(answer)

### FIXED CODE ###

N = int(input())
dic = {}
for _ in range(N):
    IN = input()
    A = "".join(sorted(list(IN)))
    if A not in dic:
        dic[A] = 1
    else:
        dic[A] += 1
answer = 0
for k,v in dic.items():
    answer += v*(v-1)//2
print(answer)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


ans = 0
for i in range(60):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    now = cnt * (N - cnt) % mod
    ans += now * mod_pow(2, i) % mod
    ans %= mod
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


ans = 0
for i in range(60):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    now = cnt * (N - cnt) % mod
    ans += now * mod_pow(2, i) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
c = 1
P = [1]
for i in range(1,k+1):
    c = A[c-1]
    if c in P:
        roop_start = P.index(c)
        roop_num = i- roop_start
        break
    P.append(c)
    if i == k:
        roop_start = '8'
        roop_num = 'b'
if roop_start == '8':
    a = k
    roop_start = 0
else:
    a = (k - roop_start) %  roop_num
b = P[a + roop_start]
print(b)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = A[now-1]
    A = [A[a-1] for a in A]
print(now)
### BUGGY CODE ###

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

N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]

def main(N, A):
    now = [-1]*N
    day = 0
    rest = N * (N-1) // 2

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(N)
        if rest == 0:
            return day

        # if not terminal make new now
        # O(N)
        for i in range(N):
            if now[i] == -1 and len(A[i]) > 0:
                now[i] = A[i].pop()
        
        # see if we have match today
        have_match = False
        # O(N)
        for i in range(N):
            if now[i] != -1 and now[now[i]-1] - 1 == i:
                now[now[i]-1] = -1
                now[i] = -1
                rest -= 1
                have_match = True
        if not have_match:
            return -1
        day += 1

print(main(N, A))

### FIXED CODE ###

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

N = int(input())
A = [[n-1 for n in list(map(int, input().split()))] + [-1] for _ in range(N)]
A = [a[::-1] for a in A]

def main(N, A):
    now = [A[i].pop() for i in range(N)]
    day = 0
    rest = N * (N-1)
    candidate = set(range(N))

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(1)
        if rest == 0:
            return day

        # see if we have match today
        # O(N)
        have_match = False
        # tmp = now.copy()
        # for i in range(N):
        #     if now[now[i]] == i:
        #         tmp[i] = A[i].pop()
        #         rest -= 1
        #         have_match = True
        # now = tmp
        change = []
        next_candidate = set()
        for i in candidate:
            if now[now[i]] == i:
                j = A[i].pop()
                change.append((i, j))
                # あとで(a, b)でnow[a] = bに更新する
                next_candidate.add(i)
                if j != -1:
                    next_candidate.add(j)
                
                rest -= 1
                have_match = True

        if len(change) == 0:
            return -1
        for (a, b) in change:
            now[a] = b
            
        candidate = next_candidate
        
        day += 1

print(main(N, A))
### BUGGY CODE ###

N = int(input())
count = 0

for i in range(357, N+1):

    i_str = str(i)

    if i_str[-1] != "3" and i_str[-1] != "5" and i_str[-1] != "7":
        continue
 
    else:
        thr = i_str.count("3")
        fiv = i_str.count("5")
        sev = i_str.count("7")


        if len(i_str) == thr + fiv + sev:
            if thr > 0:
                if fiv > 0:
                    if sev > 0: 
                        count += 1

print(count)


### FIXED CODE ###

from itertools import product

N = int(input())
num_list = ["3", "5", "7"]
count = 0

for i in range(3, 10):
    for t in (product(num_list, repeat=i)):
        check = t.count("3")*t.count("5")*t.count("7")
        if int("".join(t)) <= N and check:
            count += 1


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

from collections import defaultdict
s=input()
d=defaultdict(int)
d[0] += 1
for i in range(1,len(s)+1):
    d[int(s[-i:])%2019] += 1
ans=0
for v in d.values():
    ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
S=list(map(int,input()))
P=2019
N=len(S)
if P not in [2,5]:
  pt = [1]
  for i in range(N):
    pt.append(pt[-1]*10%P)
  dp = [(S[0]*pt[N-1])%P]
  for i in range(1,N):
    dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

  c = Counter(dp)
  ans = sum(u*(u-1)//2 for u in c.values())
  print(ans+c[0])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)
### BUGGY CODE ###

import numpy as np

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

    su = 0
    l_sum = []
    i = 0
    while (N-K) >= i:
        tmp_p = p[i:(i+K)]
        if sum(tmp_p) >= su:
            su = sum(tmp_p)
            l_sum = tmp_p
        i += 1

    ans = 0

    l_sum = np.array(l_sum)
    l_r = l_sum
    l_sum_1 = l_sum + 1
    l_sum = l_sum * l_sum_1
    l_sum = l_sum / 2
    l_sum = l_sum / l_r
    print(sum(l_sum))




    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    P_e = []
    for p in P:
        P_e.append((1 + p)/2)

    P_sum = [0]
    tmp = 0
    for i in range(N):
        tmp += P_e[i]
        P_sum.append(tmp)

    max = 0
    for i in range(K, N+1):
        tmp = P_sum[i] - P_sum[i-K]
        if tmp > max:
            max = tmp

    print(max)
    return 0
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    maxRowCount = 0
    maxRowIndexList: List[int] = []
    for row in range(H):
        counter = 0
        for item in codList:
            if item[0] == (row + 1):
                counter += 1
        if counter > maxRowCount:
            maxRowCount = counter
            maxRowIndexList = [row + 1]
        elif counter == maxRowCount:
            maxRowIndexList.append(row + 1)

    maxColumnCount = 0
    maxColumnIndexList: List[int] = []
    for column in range(M):
        counter = 0
        for item in codList:
            if item[1] == (column + 1):
                counter += 1
        if counter > maxColumnCount:
            maxColumnCount = counter
            maxColumnIndexList = [column + 1]
        elif counter == maxColumnCount:
            maxColumnIndexList.append(column + 1)

    result = maxRowCount + maxColumnCount
    for row in maxRowIndexList:
        for column in maxColumnIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

from functools import reduce
n = int(input())
tab = [int(n) for n in input().split()]
res = reduce(lambda x, y: x*y, tab)
if res > pow(10, 18):
  print("-1")
else:
  print(res)

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)
main()
### BUGGY CODE ###

H = int(input())
E = [H]
cnt = 0
while E[len(E)-1] != 0:
    if E[cnt]==1:
        E[cnt]=0
    else:
        E.append(int(E[cnt]/2))
        E.append(int(E[cnt]/2))
    cnt+=1
print(cnt)


### FIXED CODE ###

import sys
import copy
import math
import itertools

H = int(input())
cnt = 0
for i in range(int(math.log2(H))+1):
    cnt+=2**i
print(cnt)
### BUGGY CODE ###

h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

cnt = 0
ans = [["#" for i in range(w)] for j in range(h)]
while True:
    c = []
    if a == ans:
        break
    cnt += 1
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    b = c
print(cnt)

### FIXED CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
print(depth)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, D = map(int, readline().split())
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q, *LR = map(int, read().split())

    vec = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            vec[A[i][j]] = (i + 1, j + 1)

    csum = [0] * (H * W + 1)
    for i in range(1, H * W + 1):
        N = (H * W - i) // D + 1
        csum[i] = [0] * N
        for j in range(N - 1):
            csum[i][j + 1] = (
                csum[i][j]
                + abs(vec[i + (j + 1) * D][0] - vec[i + j * D][0])
                + abs(vec[i + (j + 1) * D][1] - vec[i + j * D][1])
            )

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        ans[i] = csum[l][(r - l) // D]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, D = map(int, readline().split())
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q, *LR = map(int, read().split())

    vec = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            vec[A[i][j]] = (i + 1, j + 1)
    vec[0] = vec[D]

    csum = [0] * D
    for i in range(D):
        N = (H * W - i) // D + 1
        csum[i] = [0] * N
        for j in range(N - 1):
            csum[i][j + 1] = (
                csum[i][j]
                + abs(vec[i + (j + 1) * D][0] - vec[i + j * D][0])
                + abs(vec[i + (j + 1) * D][1] - vec[i + j * D][1])
            )

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        n, m = divmod(l, D)
        ans[i] = csum[m][(r - l) // D + n] - csum[m][n]

    print('\n'.join(map(str, ans)))
    return


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

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

if '#' not in S:
    print(0)
else:
    ans = []
    for i in range(N):
        if S[i] == '#':
            ans.append(S[:i].count('#') + S[i:].count('.'))
    else:
        print(min(ans))

### FIXED CODE ###

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

white = S.count('.')
black = 0
ans = white + black

for x in S:
    if x == '.':
        white -= 1
    else:
        black += 1
    ans = min(ans, white+black)

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

n,k=map(int,input().split())
ab=[input() for i in range(n)]
a=[int(i.split()[0]) for i in ab]
b=[int(i.split()[1]) for i in ab]
c=0
for l in sorted(set(a)):
  for ind in [i for i,j in enumerate(a) if j==l]:
    c+=b[ind]
    if c>=k:
      print(a[ind])
      exit()

### FIXED CODE ###

from collections import defaultdict
n,k=map(int,input().split())
ab=[input() for i in range(n)]
d = defaultdict(list)
[d[int(i.split()[0])].append(int(i.split()[1])) for i in ab]
sd=sorted(d.items(), key=lambda x:x[0])
c=0
for i,l in sd:
  c+=sum(l)
  if c>=k:
    print(i)
    exit()
### BUGGY CODE ###

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

max_step = 0
for i in range(n):
    current_step = 0
    for j in range(i + 1, n):
        if h[j - 1] >= h[j]:
            current_step += 1
            if current_step > max_step:
                max_step = current_step
        else:
            i = j
            break
print(max_step)


### FIXED CODE ###

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

max_step = 0
current_step = 0
for i in range(n - 1):
    if h[i] >= h[i + 1]:
        current_step += 1
        if current_step > max_step:
            max_step = current_step
    else:
        current_step = 0
print(max_step)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
INF = float('inf')
dp = [INF]*N
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i+j > N-1:
            break
        dp[i+j] = min(dp[i+j], dp[i]+abs(H[i+j]-H[i]))
print(dp[N-1])


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
INF = float('inf')
dp = [INF]*N
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i+j > N-1:
            break
        dp[i+j] = min(dp[i+j], dp[i]+abs(H[i+j]-H[i]))
print(dp[N-1])
### BUGGY CODE ###

import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0]
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc.append(c_cnt)

q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)


### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))