{-# 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 qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString as BSW
import qualified Data.ByteString.Lazy.Char8 as BSL
import qualified Data.ByteString.Lazy as BSLW
import qualified Data.ByteString.Builder as BSB
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Generic as VG
import Data.Word

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

instance ShowAsBuilder Int where
  {-# INLINE showAsBuilder #-}
  showAsBuilder = BSB.intDec

v2BLines ::
  (VG.Vector v a, ShowAsBuilder a)
  => v a -> BSB.Builder
{-# INLINE v2BLines #-}
v2BLines
  = VG.foldr (\ a -> (showAsBuilder a <>) . (BSB.char7 '\n' <>)) mempty

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

IL(rIntL) :: StateT BSL.ByteString Maybe Int
rIntL = modify (BSLW.dropWhile isSpecialQuick) *> StateT BSL.readInt
IL(rIntS) :: StateT BS.ByteString Maybe Int
rIntS = modify (BSW.dropWhile isSpecialQuick) *> StateT BS.readInt

isSpecialQuick :: Word8 -> Bool
isSpecialQuick = (< fromIntegral (fromEnum '!'))

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