Buggy python submission (verdict: Runtime Error):
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [[0,0,0]]
C = []
for i in range(N):
    q = DP[i].copy()
    if S[i] == "D":
        q[0] += 1
    elif S[i] == "M":
        q[1] += 1
        q[2] += q[0]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c][2]
        else:
            ans += DP[c][2] - DP[c-k][2] - DP[c-k][0]*(DP[c][1] - DP[c-k][1])
    print(ans)

Fixed submission:
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [[0,0,0]]
C = []
for i in range(N):
    q = DP[i][:]
    if S[i] == "D":
        q[0] += 1
    elif S[i] == "M":
        q[1] += 1
        q[2] += q[0]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c][2]
        else:
            ans += DP[c][2] - DP[c-k][2] - DP[c-k][0]*(DP[c][1] - DP[c-k][1])
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [{"D":0,"M":0,"DM":0}]
C = []
for i in range(N):
    q = DP[i].copy()
    if S[i] == "D":
        q["D"] += 1
    elif S[i] == "M":
        q["M"] += 1
        q["DM"] += q["D"]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c]["DM"]
        else:
            ans += DP[c]["DM"] - DP[c-k]["DM"] - DP[c-k]["D"]*(DP[c]["M"] - DP[c-k]["M"])
    print(ans)

Fixed submission:
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [[0,0,0]]
C = []
for i in range(N):
    q = DP[i][:]
    if S[i] == "D":
        q[0] += 1
    elif S[i] == "M":
        q[1] += 1
        q[2] += q[0]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c][2]
        else:
            ans += DP[c][2] - DP[c-k][2] - DP[c-k][0]*(DP[c][1] - DP[c-k][1])
    print(ans)

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

def func(k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == "D":
            D += 1
        elif S[i] == "M":
            M += 1
            DM += D
        elif S[i] == "C":
            ans += DM
    for i in range(k,N):
        if S[i-k] == "D":
            D -= 1
            DM -= M
        elif S[i-k] == "M":
            M -= 1
        if S[i] == "D":
            D += 1
        elif S[i] == "M":
            M += 1
            DM += D
        elif S[i] == "C":
            ans += DM
    return ans
for i in K:
    print(func(i))

Fixed submission:
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [[0,0,0]]
C = []
for i in range(N):
    q = DP[i][:]
    if S[i] == "D":
        q[0] += 1
    elif S[i] == "M":
        q[1] += 1
        q[2] += q[0]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c][2]
        else:
            ans += DP[c][2] - DP[c-k][2] - DP[c-k][0]*(DP[c][1] - DP[c-k][1])
    print(ans)