program modularness
  implicit none
  integer :: k, q, n, p, r, s, i, j
  integer(8) :: d(0:5000) = 0, x, m, dj, dn, a
  read(*,*) k, q
  read(*,*) d(0:k - 1)
  do i = 1, q
    read(*,*) n, x, m
    p = (n - 1) / k
    r = mod(n - 1, k)
    dn = x
    a = n - 1
    do j = 0, k - 1
      s = p + merge(1, 0, j < r)
      dj = mod(d(j), m)
      if (dj == 0) a = a - s
      dn = dn + dj * s
    end do
    a = a - dn / m + x / m
    write(*,'(i0)') a
  end do
end program modularness