{"problem":{"name":"k-DMC","description":{"content":"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-nes","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2525,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dwacon5th_prelims_c"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $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\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S$\n$Q$\n$k_{0}$ $k_{1}$ $...$ $k_{Q-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dwacon5th_prelims_c","tags":[],"sample_group":[],"created_at":"2026-03-03 11:01:14"}}