Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i + 1] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i + 1] += 1
        acc_cnt_ab[i + 1] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = list(accumulate(acc_cnt_a))
acc_cnt_b = list(accumulate(acc_cnt_b))
acc_cnt_ab = list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = max(0, r - k)
        rejected_a = acc_cnt_a[l]
        cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
        cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
        ans += cnt_internal_ab - rejected_a * cnt_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i + 1] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i + 1] += 1
        acc_cnt_ab[i + 1] += cnt_a
acc_cnt_a = list(accumulate(acc_cnt_a))
acc_cnt_b = list(accumulate(acc_cnt_b))
acc_cnt_ab = list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r, c in enumerate(s):
        if c != 'C':
            continue
        r += 1
        l = max(0, r - k)
        rejected_a = acc_cnt_a[l]
        cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
        cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
        ans += cnt_internal_ab - rejected_a * cnt_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

n = int(input())
s = input()
cp = []
count_a = 0
accsum_ab = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
        count_a += 1
    elif c == 'M':
        cp.append((1, i))
        accsum_ab.append(count_a)
    elif c == 'C':
        cp.append((2, i))

i, j = 0, 0
while i < len(cp) and cp[i][0] != 0:
    if cp[i][0] == 1:
        j += 1
    i += 1
cp = cp[i:]
accsum_ab = accsum_ab[j:]
i, j = -1, -1
while -i <= len(cp) and cp[i][0] != 2:
    if cp[i][0] == 1:
        j -= 1
    i -= 1
if i < -1:
    cp = cp[:i + 1]
    if j < -1:
        accsum_ab = accsum_ab[:i + 1]
accsum_ab = [0] + list(accumulate(accsum_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_b = 0
    rejected_a = 0
    rejected_b = 0
    for r, item in enumerate(cp):
        if item[0] == 1:
            count_b += 1
        elif item[0] == 2:
            left_limit = item[1] - k
            while l < r and cp[l][1] <= left_limit:
                old_item = cp[l]
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    rejected_b += 1
                l += 1
            ans += accsum_ab[count_b] - accsum_ab[rejected_b] - rejected_a * (count_b - rejected_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

n = int(input())
s = input()
cp = []
count_a = 0
accsum_ab = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
        count_a += 1
    elif c == 'M':
        cp.append((1, i))
        accsum_ab.append(count_a)
    elif c == 'C':
        cp.append((2, i))

i, j = 0, 0
while i < len(cp) and cp[i][0] != 0:
    if cp[i][0] == 1:
        j += 1
    i += 1
cp = cp[i:]
accsum_ab = accsum_ab[j:]
i, j = -1, -1
while -i <= len(cp) and cp[i][0] != 2:
    if cp[i][0] == 1:
        j -= 1
    i -= 1
if i < -1:
    cp = cp[:i + 1]
    if j < -1:
        accsum_ab = accsum_ab[:i + 1]
accsum_ab = [0] + list(accumulate(accsum_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_b = 0
    rejected_a = 0
    rejected_b = 0
    for r, item in enumerate(cp):
        if item[0] == 1:
            count_b += 1
        elif item[0] == 2:
            left_limit = item[1] - k
            while l < r and cp[l][1] <= left_limit:
                old_item = cp[l]
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    rejected_b += 1
                l += 1
            ans += accsum_ab[count_b] - accsum_ab[rejected_b] - rejected_a * (count_b - rejected_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n = int(input())
s = input()
q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_a = 0
    rejected_a = 0
    count_internal_b = deque()
    sum_internal_b = 0
    for r, c in enumerate(s):
        if c == 'D':
            count_a += 1
        elif c == 'M':
            count_internal_b.append(count_a)
            sum_internal_b += count_a
        elif c == 'C':
            left_limit = r - k
            while l <= left_limit:
                old_c = s[l]
                if old_c == 'D':
                    rejected_a += 1
                elif old_c == 'M':
                    sum_internal_b -= count_internal_b.popleft()
                l += 1
            ans += sum_internal_b - rejected_a * len(count_internal_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n = int(input())
s = input()
q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_a = 0
    rejected_a = 0
    count_internal_b = deque()
    sum_internal_b = 0
    for r, c in enumerate(s):
        if c == 'D':
            count_a += 1
        elif c == 'M':
            count_internal_b.append(count_a)
            sum_internal_b += count_a
        elif c == 'C':
            left_limit = r - k
            while l <= left_limit:
                old_c = s[l]
                if old_c == 'D':
                    rejected_a += 1
                elif old_c == 'M':
                    sum_internal_b -= count_internal_b.popleft()
                l += 1
            ans += sum_internal_b - rejected_a * len(count_internal_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n = int(input())
s = input()
cp = []
count_a = 0
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
        count_a += 1
    elif c == 'M':
        cp.append((1, i, count_a))
    elif c == 'C':
        cp.append((2, i))

i = 0
while i < len(cp) and cp[i][0] != 0:
    i += 1
cp = cp[i:]
while cp and cp[-1][0] != 2:
    cp.pop()

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    rejected_a = 0
    count_internal_b = 0
    sum_internal_b = 0
    for r, item in enumerate(cp):
        # print(deq, count_a, rejected_a, count_internal_b, sum_internal_b)
        if item[0] == 1:
            count_internal_b += 1
            sum_internal_b += item[2]
        elif item[0] == 2:
            left_limit = item[1] - k
            while l < r and cp[l][1] <= left_limit:
                old_item = cp[l]
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    count_internal_b -= 1
                    sum_internal_b -= old_item[2]
                l += 1
            ans += sum_internal_b - rejected_a * count_internal_b
            # print(ans, l, r, rejected_a, count_internal_b, sum_internal_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n = int(input())
s = input()
cp = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
    elif c == 'M':
        cp.append((1, i))
    elif c == 'C':
        cp.append((2, i))

i = 0
while cp[i][0] != 0:
    i += 1
cp = cp[i:]
while cp[-1][0] != 2:
    cp.pop()

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    deq = deque()
    count_a = 0
    rejected_a = 0
    count_internal_b = 0
    sum_internal_b = 0
    for item in cp:
        # print(deq, count_a, rejected_a, count_internal_b, sum_internal_b)
        if item[0] == 0:
            count_a += 1
            deq.append(item)
        elif item[0] == 1:
            count_internal_b += 1
            sum_internal_b += count_a
            deq.append((item[0], item[1], count_a))
        else:
            left_limit = item[1] - k
            while deq and deq[0][1] <= left_limit:
                old_item = deq.popleft()
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    count_internal_b -= 1
                    sum_internal_b -= old_item[2]
            ans += sum_internal_b - rejected_a * count_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())
s = input()
cp = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
    elif c == 'M':
        cp.append((1, i))
    elif c == 'C':
        cp.append((2, i))

i = 0
while cp[i][0] != 0:
    i += 1
cp = cp[i:]
while cp[-1][0] != 2:
    cp.pop()

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    deq = deque()
    count_a = 0
    rejected_a = 0
    count_internal_b = 0
    sum_internal_b = 0
    for item in cp:
        # print(deq, count_a, rejected_a, count_internal_b, sum_internal_b)
        if item[0] == 0:
            count_a += 1
            deq.append(item)
        elif item[0] == 1:
            count_internal_b += 1
            sum_internal_b += count_a
            deq.append((*item, count_a))
        else:
            left_limit = item[1] - k
            while deq and deq[0][1] <= left_limit:
                old_item = deq.popleft()
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    count_internal_b -= 1
                    sum_internal_b -= old_item[2]
            ans += sum_internal_b - rejected_a * count_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from itertools import accumulate

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

ri = bisect.bisect(a_loc, b_loc[-1])
q = int(input())
b_acc = [0] + list(accumulate(c_acc[b] for b in b_loc))
buf = []
for k in map(int, input().split()):
    ans = 0
    pi = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a, pi)
        j = bisect.bisect(b_loc, a + k - 1, i)
        ans += c_acc[min(n, a + k)] * (j - i) - (b_acc[j] - b_acc[i])
        pi = i
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from itertools import accumulate

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
b_acc = [0] + list(accumulate(c_acc[b] for b in b_loc))
buf = []
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        ans += c_acc[min(n, a + k)] * (j - i) - (b_acc[j] - b_acc[i])
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    buf.append(ans)
print('\n'.join(map(str, buf)))


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0]
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc.append(c_cnt)

q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0]
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc.append(c_cnt)

q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0]
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc.append(c_cnt)

# print(a_loc)
# print(c_acc)

q = int(input())
for k in map(int, input().split()):
    ans = 0
    for b in b_loc:
        i = bisect.bisect_left(a_loc, max(0, b - k + 2))
        # print(b, i, a_loc[i])
        cn = c_acc[b]
        for a in a_loc[i:]:
            if a >= b:
                break
            ans += c_acc[min(a + k, n)] - cn
    print(ans)


Fixed submission:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))