Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    d = m = dm = dmc = 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

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

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = [ord(i) for i in input()]
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 68 :
                d -= 1
                dm -= m
            elif S[j] == 77 :
                m -= 1

        if S[i] == 68 :
            d += 1
        elif S[i] == 77 :
            m += 1
            dm += d
        elif S[i] == 67 :
            ret += dm
            
    print(ret)

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())
k = [int(i) for i in input().split()]

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

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

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

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

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

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

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

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()[:-1]
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            T = S[i-ki]
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            T = S[i-ki]
            if T == 'D' :
                d -= 1
                dm -= m
            elif T == 'M' :
                m -= 1

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

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

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    dp = [[0] * 3 for _ in range(ki)]
    for i in range(N) :
        j = i % ki
        dp[j][0] = dp[j-1][0]
        dp[j][1] = dp[j-1][1]
        dp[j][2] = dp[j-1][2]
        
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                dp[j][0] -= 1
                dp[j][2] -= dp[j][1]
            elif S[i-ki] == 'M' :
                dp[j][1] -= 1

        if S[i] == 'D' :
            dp[j][0] += 1
        elif S[i] == 'M' :
            dp[j][1] += 1
            dp[j][2] += dp[j][0]
        elif S[i] == 'C' :
            ret += dp[j][2]
            
    print(ret)
        

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)