{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}

import           Control.Exception (assert, evaluate)
import           Data.List         (foldl')
import           Data.Sequence     (Seq, ViewL ((:<), EmptyL), viewl, (|>))

main :: IO ()
main = do
  n <- readLn
  s <- getLine
  evaluate $ assert (length s == n) ()
  q <- readLn
  ks <- take q . map read . words <$> getLine
  putStr . unlines . map (show . (\k -> f k s)) $ ks

f :: Int -> String -> Int
f k = dmc . foldl' g (initialState k)
  where
    g state c = (countIn c (maybe id countOut c' state)) { queue = queue' }
      where
        (c', queue') = append (queue state) c

data State =
  State
  { queue :: FixedSizeQueue Char
  , d     :: !Int
  , m     :: !Int
  , dm    :: !Int
  , dmc   :: !Int
  }

initialState :: Int -> State
initialState n = State { queue = fixedSizeQueue n, d = 0, m = 0, dm = 0, dmc = 0 }

countIn :: Char -> State -> State
countIn 'D' count = count { d = d count + 1 }
countIn 'M' count = count { m = m count + 1, dm = dm count + d count }
countIn 'C' count = count { dmc = dmc count + dm count }
countIn _   count = count

countOut :: Char -> State -> State
countOut 'D' count = count { d = d count - 1, dm = dm count - m count }
countOut 'M' count = count { m = m count - 1 }
countOut _   count = count

data FixedSizeQueue a = FixedSizeQueue Int (Seq a)

fixedSizeQueue :: Int -> FixedSizeQueue a
fixedSizeQueue n = FixedSizeQueue n mempty

append :: FixedSizeQueue a -> a -> (Maybe a, FixedSizeQueue a)
append (FixedSizeQueue n q) x =
  let
    q' = q |> x
  in
    if length q' <= n
      then (Nothing, FixedSizeQueue n q')
      else case viewl q' of
             EmptyL   -> error "sequence must have more than n elements"
             y :< q'' -> (Just y, FixedSizeQueue n q'')
