output_description: Print q lines.
  
  The i-th line should contain the response to the i-th query.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      k q
      d_0 d_1 ... d_{k - 1}
      n_1 x_1 m_1
      n_2 x_2 m_2
      :
      n_q x_q m_q
attempt: def numba_compile(numba_config):
      import os, sys
  
      if sys.argv[-1] == "ONLINE_JUDGE":
          from numba import njit
          from numba.pycc import CC
  
          cc = CC("my_module")
          for func, signature in numba_config:
              vars()[func.__name__] = njit(signature)(func)
              cc.export(func.__name__, signature)(func)
          cc.compile()
          exit()
      elif os.name == "posix":
          exec(
              f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}"
          )
          for func, _ in numba_config:
              globals()[func.__name__] = vars()[func.__name__]
      else:
          from numba import njit
  
          for func, signature in numba_config:
              globals()[func.__name__] = njit(signature, cache=True)(func)
          print("compiled!", file=sys.stderr)
  
  
  import sys
  import numpy as np
  
  
  def solve(K, Q, D, NXM):
      Ans = np.empty(Q, dtype=np.int64)
      for q in range(Q):
          n, x, m = NXM[q]
          D_mod = D % m
          cnt_D0 = (D_mod == 0).sum()
          sum_D = D_mod.sum()
          t, rem = divmod(n - 1, K)
          ans = n - 1
          # print(ans)
          ans -= t * cnt_D0
          # print(f"ans={ans},t={t},rem={rem}")
  
          progress = sum_D * t
          x1 = x % m + progress
          for i in range(rem):
              d = D_mod[i]
              if d == 0:
                  ans -= 1
              x1 += d
          # print(f"D={D_mod}")
          # print(f"progress={progress},x1={x1}")
  
          ans -= x1 // m
          Ans[q] = ans
      return Ans
  
  
  numba_compile([[solve, "i8[:](i8,i8,i8[:],i8[:,:])"]])
  
  
  def main():
      K, Q = map(int, input().split())
      D = np.array(input().split(), dtype=np.int64)
      NXM = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(Q, 3)
      Ans = solve(K, Q, D, NXM)
      print("\n".join(map(str, Ans.tolist())))
  
  
  main()
  
problem_description: Statement
  
  We have a sequence of k numbers: d_0,d_1,...,d_{k - 1}.
  
  Process the following q queries in order:
  
    * The i-th query contains three integers n_i, x_i, and m_i. Let a_0,a_1,...,a_{n_i - 1} be the following sequence of n_i numbers: \begin{eqnarray} a_j = \begin{cases} x_i & ( j = 0 ) \\\ a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 < j \leq n_i - 1 ) \end{cases}\end{eqnarray} Print the number of j~(0 \leq j < n_i - 1) such that (a_j~\textrm{mod}~m_i) < (a_{j + 1}~\textrm{mod}~m_i).
  
  Here (y~\textrm{mod}~z) denotes the remainder of y divided by z, for two
  integers y and z~(z > 0).
samples: [{"input": "3 1\n    3 1 4\n    5 3 2", "output": "1\n    \n\nFor the first query, the sequence {a_j} will be 3,6,7,11,14.\n\n  * (a_0~\\textrm{mod}~2) > (a_1~\\textrm{mod}~2)\n  * (a_1~\\textrm{mod}~2) < (a_2~\\textrm{mod}~2)\n  * (a_2~\\textrm{mod}~2) = (a_3~\\textrm{mod}~2)\n  * (a_3~\\textrm{mod}~2) > (a_4~\\textrm{mod}~2)\n\nThus, the response to this query should be 1.\n\n* * *"}, {"input": "7 3\n    27 18 28 18 28 46 1000000000\n    1000000000 1 7\n    1000000000 2 10\n    1000000000 3 12", "output": "224489796\n    214285714\n    559523809"}]