Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Fixed submission:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    d = {}
    for i in range(N):
        if S[i] == 'D':
            d[i] = MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M
    res = 0
    for i in d:
        res += d[i]

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Fixed submission:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)

def cal(k):
    M = 0
    C = 0
    MC = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    d = {}
    for i in range(N):
        if S[i] == 'D':
            d[i] = MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M
    res = 0
    for i in d:
        res += d[i]

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Fixed submission:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)

def cal(k):
    M = 0
    C = 0
    MC = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    d = {}
    for i in range(N):
        if S[i] == 'D':
            d[i] = MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M
    res = 0
    for i in d:
        res += d[i]

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Fixed submission:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)
D = []
C = []
M = [0]*N
for i in range(1,N):
    M[i] = M[i-1]
    if S[i] == 'M':
        M[i] += 1
    elif S[i] == 'D':
        D.append(i)
    elif S[i] == 'C':
        C.append(i)

def cal(k): 
    j = 0
    c = C[0]
    nc = len(C)
    res = 0
    for i in range(len(D)):
        a = D[i]
        while c-a < k:
            res += M[c]-M[a]
            if j < nc-1:
                j += 1
                c = C[j
            else:
                break
    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Fixed submission:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)
D = []
C = []
M = [0]*N
for i in range(1,N):
    M[i] = M[i-1]
    if S[i] == 'M':
        M[i] += 1
    elif S[i] == 'D':
        D.append(i)
    elif S[i] == 'C':
        C.append(i)

def cal(k): 
    j = 0
    c = C[0]
    nc = len(C)
    res = 0
    for i in range(len(D)):
        a = D[i]
        while c-a < k:
            res += M[c]-M[a]
            if j < nc:
                j += 1
                c = C[j]
    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Fixed submission:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))