Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
Q=int(input())
*K,=map(int, input().split())

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

        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            ans += dm
    print(ans)


Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=tuple(input())
Q=int(input())
K=map(int,input().split())

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 submission:
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)

Buggy python submission (verdict: Runtime Error):
from collections import deque
N=int(input())
S=list(input())
Q=int(input())
K=map(int,input().split())

for k in K:
    ans=0
    d=m=dm=0
    for c in S:
        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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N=int(input())
S=input()
Q=int(input())
K=map(int,input().split())

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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N=int(input())
S=input()
Q=int(input())
K=map(int,input().split())

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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
Q=int(input())
K=map(int,input().split())

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

Fixed submission:
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)