Score : $600$ points

Problem Statement

In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short. The name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.

Given a string $S$ of length $N$ and an integer $k$ $(k \geq 3)$, he defines the k-DMC number of $S$ as the number of triples $(a, b, c)$ of integers that satisfy the following conditions:

• $0 \leq a < b < c \leq N - 1$
• $S[a]$ = D
• $S[b]$ = M
• $S[c]$ = C
• $c-a < k$

Here $S[a]$ is the $a$-th character of the string $S$. Indexing is zero-based, that is, $0 \leq a \leq N - 1$ holds.

For a string $S$ and $Q$ integers $k_0, k_1, ..., k_{Q-1}$, calculate the $k_i$-DMC number of $S$ for each $i$ $(0 \leq i \leq Q-1)$.

Constraints

• $3 \leq N \leq 10^6$
• $S$ consists of uppercase English letters
• $1 \leq Q \leq 75$
• $3 \leq k_i \leq N$
• All numbers given in input are integers

Input

Input is given from Standard Input in the following format:

$N$

$S$

$Q$

$k_{0}$ $k_{1}$ $...$ $k_{Q-1}$

Output

Print $Q$ lines. The $i$-th line should contain the $k_i$-DMC number of the string $S$.

18
DWANGOMEDIACLUSTER
1
18

1

$(a,b,c) = (0, 6, 11)$ satisfies the conditions. Strangely, Dwango Media Cluster does not have so much DMC-ness by his definition.

18
DDDDDDMMMMMCCCCCCC
1
18

210

The number of triples can be calculated as $6\times 5\times 7$.

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

0
1
2

$(a, b, c) = (0, 23, 36), (8, 23, 36)$ satisfy the conditions except the last one, namely, $c-a < k_i$. By the way, DWANGO is an acronym for "Dial-up Wide Area Network Gaming Operation".

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

10
52
110
140