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

def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

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

    X = 1
    for a in A:
        g = gcd(X, a)
        X = (X * a) // g
    ans = 0
    for a in A:
        ans = (ans + X // a)%mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from fractions import gcd
    from collections import defaultdict
    input = sys.stdin.buffer.readline

    def p(n):
        ret = defaultdict(int)
        d = 2
        m = int(n**0.5)
        while n > 1:
            if n % d == 0:
                ret[d] += 1
                n //= d
            else:
                d += 1
                if d > m:
                    ret[n] += 1
                    break
        return ret

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

    prime = defaultdict(int)
    p_list = []
    for a in A:
        pp = p(a)
        p_list.append(pp)
        for pr in pp.keys():
            ppr = prime[pr]
            pppr = pp[pr]
            if ppr < pppr:
                prime[pr] = pppr

    M = 1
    for pr in prime.keys():
        M = (M * pow(pr, prime[pr], mod))%mod

    ans = 0
    for a in A:
        ans = (ans + (M * pow(a, mod-2, mod))%mod)%mod

    print(ans)


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

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    h, w, m = map(int, input().split())
    rows = [0] * h
    cols = [0] * w
    d1 = lambda :defaultdict(int)
    d2 = defaultdict(d1)
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        rows[a-1] += 1
        cols[b-1] += 1
        d2[a-1][b-1] = 1
    rm = max(rows)
    cm = max(cols)
    rs = [i for i, v in enumerate(rows) if v == rm]
    cs = [i for i, v in enumerate(cols) if v == cm]
    r = rm + cm
    p = set()
    for rse in rs:
        for cse in cs:
            p.add(d2[rse][cse])
    r -= min(p)
    print(r)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    h, w, m = map(int, input().split())
    rows = defaultdict(int)
    cols = defaultdict(int)
    d1 = lambda :defaultdict(int)
    d2 = defaultdict(d1)
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        rows[a-1] += 1
        cols[b-1] += 1
        d2[a-1][b-1] = 1
    rm = max(rows.values())
    cm = max(cols.values())
    rs = [i for i, v in rows.items() if v == rm]
    cs = [i for i, v in cols.items() if v == cm]
    r = rm + cm
    #p = set()
    for rse in rs:
        for cse in cs:
            if d2[rse][cse] == 0:
                print(r)
                sys.exit()
    print(r-1)


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

n,k,l=map(int,input().split())
def maketree(n,k,target):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][1]
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            x=road[pidx]|road[qidx]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road.pop(z)
            for j in x:
                roadidx[j]=y
    resroad=[]
    for i in road:
        resroad.append(road[i])
    return resroad

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree=maketree(n,k,road)
metrotree=maketree(n,l,metro)
ans=[]
for i in roadtree:
    for j in metrotree:
        ans.append(i & j)

result=[1 for i in range(n)]
while len(ans)>0:
    x=ans.pop()
    for i in x:
        result[i]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
quiz = [list(map(int, input().split())) for i in range(q)]

for i in quiz:
    print(s[i[0]-1:(i[1])].count('AC'))

### FIXED CODE ###

# ACのインデックスを求める
# インデックスから、含まれる個数を求める(2分探索)
from bisect import bisect_left
N,Q = map(int, input().split())
S = input()
tmp = ''
ac_count = []
for i, c in enumerate(S):
	if tmp + c == 'AC':
		ac_count.append(i-1)
	tmp = c
ac_count.sort()

for i in range(Q):
	l, r = map(int, input().split())
	print(len(S[bisect_left(ac_count, l-1) : bisect_left(ac_count, r-1)]))
### BUGGY CODE ###

import fractions
A,B=map(int,input().split())

base=fractions.gcd(A,B)
count=1

i=2
while base!=1 or i<pow(base,1/2):
    if base%i==0:
        count+=1
        while base%i==0:
            base//=i
    i+=1
if base!=1:
    count+=1
print(count)

### FIXED CODE ###

import fractions
A,B=map(int,input().split())

base=fractions.gcd(A,B)
count=1


for i in range(2,int(pow(base,1/2)+1)):
    if base==1:
        break
    else:
        if base%i==0:
            count+=1
            while base%i==0:
                base//=i
if base!=1:
    count+=1
print(count)
### BUGGY CODE ###

# B
import numpy as np
np.random.seed(2)
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []

for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    
# find minimum degree
sv = np.array([len(G[k]) for k in range(1, N+1)])
s = np.random.choice(np.arange(N)[sv == min(sv)]) + 1

targets = dict()
for a in G[s]:
    targets[a] = 1


# BFS from st
t = G[s][0]
pt = [s, t]
del targets[t]
while len(targets) > 0:
    ques = deque()
    visited = [0]*(N+1)    
    for a in pt:
        visited[a] = 1
    ques.append([t, pt])
    end = 0
    while len(ques) > 0 and end == 0:
        q = ques.popleft()
        s = q[0]
        pt = q[1]
        for t in G[s]:
            if visited[t] == 1:
                pass
            elif t in targets.keys():
                pt.append(t)
                end = 1
                del targets[t]
                break
            else:
                visited[t] = 1
                ques.append([t, pt+[t]])
            

# BFS from end
visited = [0]*(N+1)
for a in pt:
    visited[a] = 1
sv = np.array([len([l for l in G[k] if visited[l] == 0]) if visited[k] == 0 else N for k in range(1, N+1)])

# need calculation
if len([l for l in G[t] if visited[l] == 0]) != 0:
    endp = np.random.choice(np.arange(N)[sv == min(sv)]) + 1
    targets = dict()
    for a in G[endp]:
        if visited[a] == 0:
            targets[a] = 1
    while len(targets) > 0:
        ques = deque()
        visited = [0]*(N+1)    
        for a in pt:
            visited[a] = 1
        visited[endp] = 1
        ques.append([t, pt])
        end = 0
        while len(ques) > 0 and end == 0:
            q = ques.popleft()
            s = q[0]
            pt = q[1]
            for t in G[s]:
                if visited[t] == 1:
                    pass
                elif t in targets.keys():
                    pt.append(t)
                    end = 1
                    del targets[t]
                    break
                else:
                    visited[t] = 1
                    ques.append([t, pt+[t]])
    pt.append(endp)
        
print(len(pt))
print(" ".join([str(a) for a in pt]))

### FIXED CODE ###

# B
import numpy as np
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []
    
visited = [0]*(N+1)
for m in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    if m == 0:
        pt = [A, B]
        visited[A] = 1
        visited[B] = 1

# from left
s = pt[0]
add_left = list()

while True:
    left_ext = [l for l in G[s] if visited[l] == 0]
    if len(left_ext) != 0:
        s = left_ext[0]
        visited[s] = 1
        add_left.append(s)
    else:
        break

# from right
s = pt[1]
add_right = list()

while True:
    right_ext = [l for l in G[s] if visited[l] == 0]
    if len(right_ext) != 0:
        s = right_ext[0]
        visited[s] = 1
        add_right.append(s)
    else:
        break
pt = list(reversed(add_left)) + pt + add_right
print(len(pt))
print(" ".join([str(a) for a in pt]))
### BUGGY CODE ###

import fractions

def process():
    n = int(raw_input().strip())
    for x in xrange(1, 3501):
        for y in xrange(x, 3501):
            b = x*y/fractions.gcd(x, y)
            b = b*n/fractions.gcd(b, n)
            a = b*4/n
            a -= b/x
            a -= b/y
            r = fractions.gcd(a, b)
            a /= r
            b /= r
            if a==1:
                print str(x)+' '+str(y)+' '+str(b)
                return

process()

### FIXED CODE ###

def gcd(x, y):
    while y!=0:
        x, y = y, x%y
    return x

def process():
    n = int(raw_input().strip())
    if n%2 == 0:
        print str(n)+' '+str(n)+' '+str(n>>1)
        return
    for x in xrange(max(n>>1, 1), 3501):
        for y in xrange(x, 3501):
            b = n*x*y
            a = 4*x*y-n*x-n*y
            if a>0 and (b%a)==0:
                print str(x)+' '+str(y)+' '+str(b/a)
                return

process()
### BUGGY CODE ###

N = int(input())
S = [str(input()) for i in range(N)]

S = sorted(S)
count = 0
first = 0
removecount = 0

for i in range(N):
    j = 0
    while first + count + 1 < len(S) :
        if S[first]==S[first+1+j]:
            S[first+1+j] = "nullsad"
            count+=1
            j += 1
        else:
            first += count + 1
            removecount += count
            count = 0
            break

for i in range(removecount + count):
    S.remove("nullsad")

print(len(S))


### FIXED CODE ###

N = int(input())
S = [str(input()) for i in range(N)]

S = sorted(S)
count = 0
first = 0
removecount = 0

for i in range(N):
    j = 0
    while first + count + 1 < len(S) :
        if S[first]==S[first+1+j]:
            S[first+1+j] = "null"
            count+=1
            j += 1
        else:
            first += count + 1
            removecount += count
            count = 0
            break

print(len(S)-S.count("null"))
### BUGGY CODE ###

N, M = map(int, input().split())
A = set(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, int(str(j)+str(an)))
    ans[i] = x
print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in A:
        k = num[j - 1]
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        an = ans[i - k]
        if an == 0:
            continue
        x = max(x, an * 10 + j)
    ans[i] = x
print(ans[N])
### BUGGY CODE ###

from heapq import *
import sys
input=sys.stdin.readline
def main():
  N,M=map(int,input().split())
  G=[set() for i in range(N)]
  for i in range(M):
      u,v=map(int,input().split())
      u,v=u-1,v-1
      G[u].add(v)
  S,T=map(int,input().split())
  A=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          A[i]=A[i] | G[v]
  B=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          B[i]=B[i] | A[v]
  """
  C=[[] for i in range(N)]
  for i in range(N):
      for j in B[i]:
          C[i].append([j,1])
  """
  INF=10**9+7
  def dijkstra(G,s):

    d=[INF]*N
    d[s]=0
    visited={s}
    que=[(0,s)]
    while(que):
      p=heappop(que)
      v=p[1]
      visited.add(v)
      for node in G[v]:
        cost=1
        if (node not in visited) and d[node]>d[v]+cost:
          d[node]=d[v]+cost
          heappush(que,(d[node],node))
    return d
  d=dijkstra(B,S-1)
  if d[T-1]==INF:
    print(-1)
  else:
    print(d[T-1])
if __name__=='__main__':#おまじない
  main()


### FIXED CODE ###

from heapq import *
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[[] for i in range(3*N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[3*u+0].append([3*v+1,0])
    G[3*u+1].append([3*v+2,0])
    G[3*u+2].append([3*v+0,1])
S,T=map(int,input().split())
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*(3*N)
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(G,(S-1)*3)
if d[(T-1)*3]==INF:
  print(-1)
else:
  print(d[(T-1)*3])
### BUGGY CODE ###

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

for i in range(n-k+1):
    xtmp = x[i:i+k]
#     print(i, xtmp)

    if i==0:
        MIN = abs(xtmp[0])+2*abs(xtmp[-1])

    MIN = min(MIN, abs(xtmp[0]-xtmp[-1]) + abs(xtmp[0]))
    MIN = min(MIN, abs(xtmp[0]-xtmp[-1]) + abs(xtmp[-1]))

print(MIN)

### FIXED CODE ###

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

n, k = map(int, input().split())
X = list(map(int, input().split()))
ans = 10**10
for i in range(n-k+1):
    left = X[i]
    right = X[i+k-1]
    ans = min(ans, abs(left)+abs(left-right), abs(right)+abs(right-left))
print(ans)
### BUGGY CODE ###

N = int(input())

A = []
max1 = 0
max2 = 0

for i in range(N):
  B = int(input())
  if B>max1:
    max1 = B
  else:
    if B>max2:
      max2 = B
      
  A.append(B) 

for i in range(N):
  if A[i] == max(A):
    print(max2)
  else:
    print(max1)


### FIXED CODE ###

N = int(input())

A = []
max1 = 0
max1i = 0
max2 = 0
max2i = 0

for i in range(N):
  B = int(input())
  if B>max1:
    max1i = i
    max1 = B
  else:
    if B>max2:
      max2 = B
      max2i = i

for i in range(N):
  A.append(max1)
A[max1i] = max2

for i in range(N):
  print(A[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ad = {}
for i in a:
  if i not in ad:
  	ad[i] = a.count(i)
q = int(input())
ll = []
for i in range(q):
	l = list(map(int, input().split()))
	ll.append(l)
	if l[1] not in ad:
		ad[l[1]] = 0

for i in ll:
  if i[0] in ad:
    ad[i[1]] = ad[i[1]] + ad[i[0]]
    ad[i[0]] = 0
    adsum = 0
    for j in ad:
      adsum += j*ad[j]
    print(adsum)
  else:
    adsum = 0
    for j in ad:
      adsum += j*ad[j]
    print(adsum)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [list(map(int,input().split(" "))) for i in range(0,q)]

ans = sum(a)
anum = collections.Counter(a)

for i in range(q):
    x, y = b[i][0], b[i][1]
    ans += anum[x] * (y - x)
    anum[y] += anum[x]
    anum[x] = 0
    print(ans)
### BUGGY CODE ###

def calc(array, start, k):
    ri = start
    li = start
    
    if start == 0:
        eri = len(array) - 1
        eli = start + 1
    elif start == len(array) - 1:
        eri = start - 1
        eli = 0
    else:
        eri = start - 1
        eli = start + 1
    
    right = 0
    left = 0

    while True:
        if ri + 1 == len(array):
            right += k - array[ri] + array[0]
            ri = 0
        else:
            right += array[ri + 1] - array[ri]
            ri += 1

        if li - 1 < 0:
            left += k - array[-1] + array[li]
            li = len(array) - 1
        else:
            left += array[li] - array[li - 1]
            li -= 1
        #print("start = {}: ri = {}, li = {}".format(start, ri, li))
        #print("right = {}, left = {}".format(right, left))

        if ri == eri and li == eli:
            break

    return min(right, left)

def main():
    tmp = input().split(" ")
    k = int(tmp[0])

    a = input().split(" ")
    a = [int(i) for i in a]

    ans = 300000000
    for i in range(len(a)):
        ans = min(ans, calc(a, i, k))

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    tmp = input().split(" ")
    k = int(tmp[0])

    a = input().split(" ")
    a = [int(i) for i in a]

    ans = []
    for i in range(len(a)):
        if i == 0:
            ans.append(k - a[-1] + a[i])
        else:
            ans.append(a[i] - a[i - 1])
        
    print(sum(ans) - max(ans))


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

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

for i in range(K):
  a = [0] * N
  for n, A_n in enumerate(A):
    b = [0] * N
    b_min = 0 if n-A_n < 0 else n-A_n
    b_max = N-1 if n+A_n > N-1 else n+A_n

    for j in range(b_min, b_max+1):
      b[j] = 1
    a = [ x + y for (x, y) in zip(a, b)]
  A = a

print(" ".join(list(map(str, A))))

### FIXED CODE ###

import math

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

for i in range(min(41, K)):
  B = [0] * N
  for n, A_n in enumerate(A):
    B_min = max(0, n-A_n)
    b_max = min(N-1, n+A_n)
    B[B_min] += 1
    if b_max+1 < N:
      B[b_max+1] -= 1
  
  sum = 0
  for n in range(len(A)):
    sum += B[n]
    A[n] = sum

print(" ".join(list(map(str, A))))
### BUGGY CODE ###

a,b,c,d = map(int, input().split())
#print(a,b,c,d)
l = []
for i in range(a,b+1):
    l.append(i)
#print(l)
x = 0
for j in l:
    if j%c!=0 and j%d!=0:
        x += 1
print(x)



### FIXED CODE ###

import fractions

a,b,c,d = map(int, input().split())
#print(a,b,c,d)
total = b-a+1
#print(total)
lcm = int(c*d / fractions.gcd(c,d))
#print(lcm)
x = (b//c) + (b//d) - (b//lcm)
y = ((a-1)//c) + ((a-1)//d) - ((a-1)//lcm)
#print(x,y)
print(total - (x - y))
### BUGGY CODE ###

A,B = map(int,input().split())
ans = A
for i in range(A+1,B+1):
    ans ^= i
print(ans)

### FIXED CODE ###

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

At = A%4
Bt = B%4

ans = 0
if At>0:
    for i in range(4-At):
        ans ^= A+i
if Bt<4:
    for i in range(Bt+1):
        ans ^= B-i
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]-1].append(x[i][1]-1)
    adj[x[i][1]-1].append(x[i][0]-1)

global ans
ans = [0]*N

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(0, 0)

for i in range(N):
    print(ans[i], '', end='')

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


for i in range(1, N+1):
    print(ans[i], ' ', end='')
'''

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

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

que = deque()
ans = [0]*N

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        if next != v[0]:
            que.append((v[1], next))

for k in ans:
    print(k, '', end='')
### BUGGY CODE ###

N=int(input())
S=tuple(map(ord,input()))
Q=int(input())
K=map(int,input().split())
D,M,C=map(ord,'DMC')

for k in K:
    ans=0
    d=m=dm=0
    for i in range(N):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
        if i>=k-1:
            c=S[i-(k-1)]
            if c==D:
                d-=1
                dm-=m
            elif c==M:
                m-=1
    print(ans)

### FIXED CODE ###

N=int(input())
S=tuple(map(ord,input()))
Q=int(input())
K=map(int,input().split())
D,M,C=map(ord,'DMC')

for k in K:
    ans=0
    d=m=dm=0
    for i in range(min(k-1,N)):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
    for i in range(k-1,N):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
        c=S[i-(k-1)]
        if c==D:
            d-=1
            dm-=m
        elif c==M:
            m-=1
    print(ans)