Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            dd, mm, dmm = dp[ll]
            As[j] += dm - dmm - dd*(m-mm)
    dp.append([d,m,dm])
for a in As:
    print(a)


Fixed submission:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            dd, mm, dmm = dp[ll]
            As[j] += dm - dmm - dd*(m-mm)
    dp.append([d,m,dm])
for a in As:
    print(a)


Fixed submission:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            dd, mm, dmm = dd[ll]
            As[j] += dm - dmm - dd*(m-mm)
    dp.append([d,m,dm])
for a in As:
    print(a)


Fixed submission:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - dp[ll][2] - dp[ll][0]*(m-dp[ll][1])
    dp.append([d,m,dm])
for a in As:
    print(a)


Fixed submission:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0] for _ in range(N+1)]
As = [0]*qn
for i, c in enumerate(S):
    i += 1
    dp[i][0] = dp[i-1][0] + (c=="D")
    dp[i][2] = dp[i-1][2] + (c=="M")
    dp[i][1] = dp[i-1][1] + (c=="M")*dp[i-1][0]
    if c != "C":
        continue
    for j, q in enumerate(qs):
        ll = max(i-q, 0)
        As[j] += dp[i-1][1] - dp[ll][1] - dp[ll][0]*(dp[i-1][2]-dp[ll][2])
for a in As:
    print(a)


Fixed submission:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)

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


dp = [[0,0,0,0] for _ in range(N+1)]
As = [0]*qn
for i, c in enumerate(S):
    i += 1
    if c == "D":
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
    if c == "M":
        dp[i][1] = dp[i-1][1] + dp[i-1][0]
        dp[i][3] = dp[i-1][3] + 1
    else:
        dp[i][1] = dp[i-1][1]
        dp[i][3] = dp[i-1][3]
    if c == "C":
        dp[i][2] = dp[i-1][2] + dp[i-1][1]
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
#            print(i, i-1, i-q, q)
#            print(dp[i-1], dp[ll]) 
            As[j] += dp[i-1][1] - dp[ll][1] - (dp[ll][0]*(dp[i-1][3]-dp[ll][3]))
    else:
        dp[i][2] = dp[i-1][2]
for a in As:
    print(a)
#print(dp)


Fixed submission:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)