Problem Description

Dwango's content delivery infrastructure system, Dwango Media Cluster, is abbreviated as DMC.
Niwango, who finds this name cool, decided to define the DMC-ness of a string as a numerical value.
Specifically, given a string \( S \) of length \( N \) and an integer \( k \) of at least 3, the number of integer triples \( (a, b, c) \) that satisfy the following conditions is called the \( k \)-DMC number of \( S \).

• \( 0 \leq a \)
• \( S[a] = \) D
• \( S[b] = \) M
• \( S[c] = \) C
• \( c - a \)

Here, \( S[a] \) represents the \( a \)-th character of \( S \). The first character is treated as the 0-th character (i.e., \( 0 \leq a \leq N - 1 \)).

For a given string \( S \) and \( Q \) integers \( k_0, k_1, \ldots, k_{Q-1} \), calculate the \( k_i \)-DMC number for each \( k_i \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( S \) \( Q \) \( k_0 \) \( k_1 \) \( \ldots \) \( k_{Q-1} \)

Output Format

Output \( Q \) lines.
The \( i \)-th line (\( 0 \leq i \leq Q-1 \)) should contain the \( k_i \)-DMC number of the string \( S \).

Sample Input and Output

Sample Input #1

18
DWANGOMEDIACLUSTER
1
18

Sample Output #1

1

Sample Input #2

18
DDDDDDMMMMMCCCCCCC
1
18

Sample Output #2

210

Sample Input #3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

Sample Output #3

0
1
2

Sample Input #4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

Sample Output #4

10
52
110
140

Notes/Hints

Constraints

• \( 3 \leq N \leq 10^6 \)
• \( S \) is a string consisting of characters A - Z
• \( 1 \leq Q \leq 75 \)
• \( 3 \leq k_i \leq N \)
• All numbers given as input are integers

Sample Explanation 1

\( (a, b, c) = (0, 6, 11) \) satisfies the conditions. It seems that Dwango Media Cluster is not very DMC-like according to Niwango's definition.

Sample Explanation 2

There are \( 6 \times 5 \times 7 \) possible combinations.

Sample Explanation 3

The conditions other than \( c - a \) are satisfied by \( (a, b, c) = (0, 23, 36), (8, 23, 36) \). By the way, DWANGO stands for "Dial-up Wide Area Network Gaming Operation".

见题面 Input 部分

见题面 Output 部分