{-# LANGUAGE
  ScopedTypeVariables, BangPatterns, TupleSections, ExplicitForAll,
  LambdaCase, MultiWayIf, Unsafe, RecordWildCards, FlexibleContexts, CPP,
  NoMonomorphismRestriction, GADTs, PatternGuards, MagicHash, UnboxedTuples,
  RankNTypes, EmptyDataDecls, EmptyCase, ViewPatterns, PolyKinds,
  TypeFamilies, OverloadedStrings, FlexibleInstances, UndecidableInstances,
  DefaultSignatures, GeneralizedNewtypeDeriving, StandaloneDeriving,
  DeriveGeneric, DeriveFunctor, DeriveDataTypeable, DeriveFoldable,
  DeriveTraversable, DeriveDataTypeable, FlexibleInstances,
  MultiParamTypeClasses #-}
{-# OPTIONS_GHC -O2 #-}

import Prelude
import System.IO
import Control.Applicative
import Control.Monad.State.Strict
import Data.Monoid
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import qualified Data.ByteString.Builder as BSB
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Generic as VG

main :: IO ()
main = do
  [k,q] <- map readInt . words <$> getLine
  !ds <- getVecULn k rIntS
  printVecInLines =<< getVecURest q (liftA3 (query ds) rIntL rIntL rIntL)

query :: VU.Vector Int -> Int -> Int -> Int -> Int
query !ds !n !x !m = VU.ifoldr
      (\ !i !dj cont !cnt0 !tot ->
         let !cnt = if i < offCycle then numCycles+1 else numCycles
         in if dj == 0 then (cont $! cnt0 + cnt) tot
                       else cont cnt0 $! tot + dj * cnt)
      (\ !cnt0 !aLast -> (n-1) - (cnt0 + aLast `quot` m - a0 `quot` m))
      dsModded 0 x
  where
    dsModded = VU.map (`rem` m) ds
    !a0 = x
    !(!numCycles,!offCycle) = divMod (n-1) (VU.length ds)

#define IL(f) {-# INLINE f #-}; f

printVecInLines ::
  (VG.Vector v a, ShowAsBuilder a) => v a -> IO ()
IL(printVecInLines) = BSB.hPutBuilder stdout . v2BLines

class ShowAsBuilder a where
  showAsBuilder :: a -> BSB.Builder

#define INS(t,f) instance ShowAsBuilder t where { IL(showAsBuilder)=f }
INS(Int,BSB.intDec)
#undef INS

v2BLines ::
  (VG.Vector v a, ShowAsBuilder a)
  => v a -> BSB.Builder
IL(v2BLines) = v2BLinesWith showAsBuilder


v2BLinesWith ::
  (VG.Vector v a)
  => (a -> BSB.Builder) -- ^ show function
  -> v a -> BSB.Builder
IL(v2BLinesWith) showFct
  = VG.foldr (\ a -> (showFct a <>) . (BSB.char7 '\n' <>)) mempty


IL(getVecGLn) :: (VG.Vector v a) =>
  Int -> StateT BS.ByteString Maybe a -> IO (v a)
getVecGLn n s = VG.unfoldrN n (runStateT s) <$> BS.getLine
IL(getVecGRest) :: (VG.Vector v a) =>
  Int -> StateT BSL.ByteString Maybe a -> IO (v a)
getVecGRest n s = VG.unfoldrN n (runStateT s) <$> BSL.getContents
IL(getVecULn) :: (VU.Unbox a) =>
  Int -> StateT BS.ByteString Maybe a -> IO (VU.Vector a)
getVecULn = getVecGLn
IL(getVecURest) :: (VU.Unbox a) =>
  Int -> StateT BSL.ByteString Maybe a -> IO (VU.Vector a)
getVecURest = getVecGRest

IL(rIntL) :: StateT BSL.ByteString Maybe Int
rIntL = skipSpecialL $ StateT BSL.readInt
IL(rIntS) :: StateT BS.ByteString Maybe Int
rIntS = skipSpecialS $ StateT BS.readInt
IL(dropSpecialL) :: (MonadState BSL.ByteString m) => m ()
dropSpecialL = modify $ BSL.dropWhile (<'!')
IL(dropSpecialS) :: (MonadState BS.ByteString m) => m ()
dropSpecialS = modify $ BS.dropWhile (<'!')
IL(skipSpecialL) :: (MonadState BSL.ByteString m) => m a -> m a
skipSpecialL = (dropSpecialL *>)
IL(skipSpecialS) :: (MonadState BS.ByteString m) => m a -> m a
skipSpecialS = (dropSpecialS *>)

readInt :: String -> Int
{-# INLINE readInt #-}
readInt = read


Measured memory_bytes: 1532