题目描述

Dwango公司有一个名为“Dwango Media Cluster”的内容分发系统，简称为“DMC”。在Niwango君看来，“DMC”这个名字很酷，所以他开始定义字符串的“DMC特性”。

给定一个长度为N的字符串S和一个整数k $(k \geq 3)$，他将S的_$k-DMC数$_定义为满足以下条件的整数三元组$(a, b, c)$的个数：

• $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}$，计算出每个i $(0 \leq i \leq Q-1)$对应的$k_i-DMC数$。

约束条件

• $3 \leq N \leq 10^6$
• $S$由大写英文字母组成
• $1 \leq Q \leq 75$
• $3 \leq k_i \leq N$
• 输入中给出的所有数字都是整数

输入

输入按以下格式从标准输入中给出。

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

输出

输出答案。

输入示例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

$(a, b, c) = (0, 23, 36), (8, 23, 36)$满足除最后一个条件$c-a < k_i$之外的所有条件。
顺便说一下，DWANGO是“Dial-up Wide Area Network Gaming Operation”的首字母缩写。

输入示例4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

输出示例4

10
52
110
140