{"raw_statement":[{"iden":"problem statement","content":"In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short.  \nThe name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.\nGiven 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:\n\n*   $0 \\leq a < b < c \\leq N - 1$\n*   $S[a]$ = `D`\n*   $S[b]$ = `M`\n*   $S[c]$ = `C`\n*   $c-a < k$\n\nHere $S[a]$ is the $a$\\-th character of the string $S$. Indexing is zero-based, that is, $0 \\leq a \\leq N - 1$ holds.\nFor 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)$."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 10^6$\n*   $S$ consists of uppercase English letters\n*   $1 \\leq Q \\leq 75$\n*   $3 \\leq k_i \\leq N$\n*   All numbers given in input are integers"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S$\n$Q$\n$k_{0}$ $k_{1}$ $...$ $k_{Q-1}$"},{"iden":"sample input 1","content":"18\nDWANGOMEDIACLUSTER\n1\n18"},{"iden":"sample output 1","content":"1\n\n$(a,b,c) = (0, 6, 11)$ satisfies the conditions.  \nStrangely, Dwango Media Cluster does not have so much DMC-ness by his definition."},{"iden":"sample input 2","content":"18\nDDDDDDMMMMMCCCCCCC\n1\n18"},{"iden":"sample output 2","content":"210\n\nThe number of triples can be calculated as $6\\times 5\\times 7$."},{"iden":"sample input 3","content":"54\nDIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED\n3\n20 30 40"},{"iden":"sample output 3","content":"0\n1\n2\n\n$(a, b, c) = (0, 23, 36), (8, 23, 36)$ satisfy the conditions except the last one, namely, $c-a < k_i$.  \nBy the way, DWANGO is an acronym for \"Dial-up Wide Area Network Gaming Operation\"."},{"iden":"sample output 4","content":"30\nDMCDMCDMCDMCDMCDMCDMCDMCDMCDMC\n4\n5 10 15 20"},{"iden":"sample output 4","content":"10\n52\n110\n140"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}