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$.

Sample Input 1

18
DWANGOMEDIACLUSTER
1
18

Sample Output 1

1

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

Sample Input 2

18
DDDDDDMMMMMCCCCCCC
1
18

Sample Output 2

210

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

Sample Input 3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

Sample Output 3

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".

Sample Output 4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

Sample Output 4

10
52
110
140