問題文

ドワンゴのコンテンツ配信基盤システム Dwango Media Cluster は、略して DMC と呼ばれています。
この名前をかっこ良いと感じたニワンゴくんは、文字列の DMC らしさを数値として定義することにしました。
具体的には、長さ $N$ のある文字列 $S$ と3以上の整数 $k$ が与えられた時、以下を満たす整数の3つ組 $(a,b,c)$ の個数を $S$ の $k$-DMC 数と呼ぶことにします。

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

ここで、S\[a\] は $S$ の $a$ 番目の文字を表します。先頭の文字は $0$ 文字目として扱います (つまり、$0 \\leq a \\leq N - 1$ です)。

ある文字列 $S$ と $Q$ 個の整数 $k_0, k_1, ..., k_{Q-1}$ に対して、$k_i$-DMC 数をそれぞれ計算してください。

制約

• $3 \\leq N \\leq 10^6$
• $S$ はA - Z からなる文字列
• $1 \\leq Q \\leq 75$
• $3 \\leq k_i \\leq N$
• 入力として与えられる数値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$Q$ 行出力せよ。
$i$ 行目 $(0 \\leq i \\leq Q-1)$ には、文字列 $S$ の $k_i$-DMC 数を出力せよ。

入力例1

18
DWANGOMEDIACLUSTER
1
18

出力例1

1

$(a,b,c) = (0, 6, 11)$ が条件を満たします。
Dwango Media Cluster は、ニワンゴくんの定義では意外と DMC らしくないようです。

入力例2

18
DDDDDDMMMMMCCCCCCC
1
18

出力例2

210

$6\\times 5\\times 7$ 個の組み合わせがありえます。

入力例3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

出力例3

0
1
2

$c-a < k_i$ 以外の条件は $(a, b, c) = (0, 23, 36), (8, 23, 36)$ が満たします。
ちなみに、DWANGO は「Dial-up Wide Area Network Gaming Operation」の頭文字です。

入力例4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

出力例4

10
52
110
140