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 f_modularness():
      K, Q = [int(i) for i in input().split()]
      D = [int(i) for i in input().split()]
      Queries = [[int(i) for i in input().split()] for j in range(Q)]
  
      def divceil(a, b):
          return (a + b - 1) // b
  
      ans = []
      for n, x, m in Queries:
          last, eq = x, 0  # 末項、D_i % m == 0 となる D_i の数
          for i, d in enumerate(D):
              num = divceil(n - 1 - i, K)  # D_i を足すことは何回起きるか？
              last += (d % m) * num
              if d % m == 0:
                  eq += num
          ans.append((n - 1) - (last // m - x // m) - eq)
      return "\n".join(map(str, ans))
  
  
  print(f_modularness())
  
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"}]