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).

-----Constraints-----
 - All values in input are integers.
 - 1 \leq k, q \leq 5000
 - 0 \leq d_i \leq 10^9
 - 2 \leq n_i \leq 10^9
 - 0 \leq x_i \leq 10^9
 - 2 \leq m_i \leq 10^9

-----Input-----
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

-----Output-----
Print q lines.
The i-th line should contain the response to the i-th query.

-----Sample Input-----
3 1
3 1 4
5 3 2

-----Sample Output-----
1

For the first query, the sequence {a_j} will be 3,6,7,11,14.
 - (a_0~\textrm{mod}~2) > (a_1~\textrm{mod}~2)
 - (a_1~\textrm{mod}~2) < (a_2~\textrm{mod}~2)
 - (a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)
 - (a_3~\textrm{mod}~2) > (a_4~\textrm{mod}~2)
Thus, the response to this query should be 1.

Difficulty: interview

Starter code:

Solutions:
import numpy as np

k, q = map(int, input().split())
d = np.array(list(map(int, input().split())))

for i in range(q):
  n, x, m = map(int, input().split())
  mod_d = d % m
  modsum_d = mod_d.cumsum()
  _q, _m = divmod(n - 1, k)
  
  ans = modsum_d[k - 1] * _q
  if _m > 0:
    ans += modsum_d[_m - 1]
  ans = n - 1 - (ans + x % m) // m - np.count_nonzero(mod_d == 0) * _q
  if _m > 0:
    ans -= np.count_nonzero(mod_d[0 : _m] == 0)
  print(ans)

import numpy as np

k,q = map(int,input().split())
d = np.array(list(map(int,input().split())))
n = [0]*q
x = n.copy()
m = n.copy()
for i in range(q):
    n[i],x[i],m[i] = map(int,input().split())
    
for i in range(q):
    d_ = d%m[i]
    j = np.sum(d_ * ((n[i]-1)//k)) + np.sum(d_[:(n[i]-1)%k])
    s = np.sum(np.sum(d_==0) * ((n[i]-1)//k)) + np.sum(d_[:(n[i]-1)%k]==0)
    count = n[i] - 1 - (j+x[i]%m[i])//m[i] - s
    print(count)

def main():
  import numpy as np
  k, q = map(int, input().split())
  d = np.array(list(map(int, input().split())))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = d % m
    zero_d = k - np.count_nonzero(d_mod)
    d_mod_sum = np.sum(d_mod) + m * zero_d
    rep = (n-1) // k
    rem = (n-1) % k
    zero_rem = len(d_mod[:rem]) - np.count_nonzero(d_mod[:rem])
    rem_sum = np.sum(d_mod[:rem]) + m * zero_rem
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
def __starting_point():
  main()
__starting_point()

from numpy import int64, count_nonzero

K, Q, *I = map(int, open(0).read().split())
D, NXM = int64(I[:K]), I[K:]

for n, x, m in zip(*[iter(NXM)] * 3):
    q, r = divmod(n - 1, K)
    T = D % m

    a = (K - count_nonzero(T)) * q + r - count_nonzero(T[:r])
    b = (x % m + T.sum() * q + T[:r].sum()) // m

    print(n - 1 - a - b)

k,q = input().split()
k = int(k)
q = int(q)

d = input().split()
for i in range(k):
    d[i] = int(d[i]) - 1

import numpy as np
d = np.array(d)

for r in range(q):
    n,x,m = input().split()
    n = int(n)
    x = int(x)
    m = int(m)

    dd = d % m + np.ones(k,dtype="int")
    DD = np.concatenate((np.zeros(1, dtype="int"),np.cumsum(dd) ))
    
    alast = x + DD[k]*((n-1)//k) + DD[(n-1)%k]
    kuriagari = alast // m - x//m

#    print([x%m, alast, alast%m, n - kuriagari - 1])
    print (n - 1 - kuriagari)

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
import numpy as np
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))
    d = np.array(d, dtype=np.uint64)

    def check(n ,x, m):
        _d = d % m
        d0 = d % m == 0
        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[:n_rest].sum()
            d0_rest = d0[:n_rest].sum()

        a_last = x + n_d * _d.sum() + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0.sum() + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(int(check(n, x, m)))

def __starting_point():
    run()
__starting_point()

import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	k,q = MI()
	d = LI()
	d = np.array(d)
	ans = [0]*q
	for i in range(q):
		n,x,m = MI()
		d_modm = d%m
		zero = ((n-1)//k)*np.sum(d_modm==0) + np.sum((d_modm==0)[:(n-1)%k])
		last = x + ((n-1)//k)*np.sum(d_modm) + np.sum((d_modm)[:(n-1)%k])
		ans[i]=(n-1)-zero-(last//m-x//m)
	printV(ans)

def __starting_point():
	main()
__starting_point()

import numpy as np


k, q = list(map(int, input().split()))
d = np.array(list(map(int, input().split())), dtype=np.int64)
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = d % m
    rem_d_mod = d_mod[: (n - 1) % k]
    print((n - 1 - (x % m + ((n - 1) // k) * np.sum(d_mod) + np.sum(rem_d_mod)) // m
          - ((n - 1) // k) * np.count_nonzero(d_mod == 0) - np.count_nonzero(rem_d_mod == 0)))


import numpy as np
k, q = list(map(int, input().split()))
d = np.array(list(map(int, input().split())))
for _ in range(q):
    n, x, m = list(map(int, input().split()))
    dm = d % m
    a = (n - 1) % k
    ans = n - 1
    ans -= np.count_nonzero(dm[:a] == 0) * ((n - 1) // k + 1)
    ans -= np.count_nonzero(dm[a:] == 0) * ((n - 1) // k)
    ans -= (x % m + np.sum(dm[:a]) * ((n - 1) // k + 1) + np.sum(dm[a:]) * ((n - 1) // k)) // m
    print(ans)



import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    k,q=MI()
    dd=LI()
    dd=np.array(dd,dtype="i8")
    for _ in range(q):
        n,x,m=MI()
        cc=dd%m
        zall=np.sum(cc==0)
        zlast=np.sum(cc[:(n-1)%k]==0)
        s=np.sum(cc)*((n-1)//k)
        r=np.sum(cc[:(n-1)%k])
        last=x%m+s+r
        no=last//m
        print(n-1-no-zall*((n-1)//k)-zlast)

main()


import numpy as np


def solve(k, q, d_list, query_list):

    res = []
    d_arr = np.array(d_list)
    for query in query_list:
        n, x, m = query
        d_arr_mod = (d_arr - 1) % m + 1
        x = x % m
        a_n1 = x + ((n - 1) // k) * d_arr_mod.sum() + d_arr_mod[:((n - 1) % k)].sum()
        res.append(n - 1 - a_n1 // m)

    return res


def main():
    k, q = list(map(int, input().split()))
    d_list = list(map(int, input().split()))
    query_list = [list(map(int, input().split())) for _ in range(q)]
    res = solve(k, q, d_list, query_list)
    for r in res:
        print(r)


def test():
    assert solve(3, 1, [3, 1, 4], [(5, 3, 2)]) == [1]
    assert solve(7, 3, [27, 18, 28, 18, 28, 46, 1000000000], [
        (1000000000, 1, 7), (1000000000, 2, 10), (1000000000, 3, 12)]) == [224489796, 214285714, 559523809]


def __starting_point():
    # test()
    main()

__starting_point()

def main():
    import numpy as np
    k, q = list(map(int, input().split()))
    d = np.array(list(map(int, input().split())), dtype=np.int64)
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = np.sum((d[:(n-2) % k+1]-1) % m+1)
        d3 = np.sum((d[(n-2) % k+1:]-1) % m+1)
        print((n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m))


main()


import numpy as np

def main():
    k, q = [int(x) for x in input().split()]
    d = np.fromstring(input(), np.int64, sep=' ')

    def solve1(d, n):
        # 同じ場合
        zero = np.where(d == 0)[0]
        n_zero = zero.shape[0] * ((n - 1) // k)
        n_zero += np.count_nonzero(zero < (n - 1) % k)
        return n_zero

    def solve2(d, n, x, m):
        # 小さくなる場合
        a_max = np.sum(d) * ((n - 1) // k) + np.sum(d[:(n - 1) % k])
        return (a_max + x) // m - x // m

    for _ in range(q):
        n, x, m = [int(x) for x in input().split()]
        dm = d % m
        n_zero = solve1(dm, n)
        n_dec = solve2(dm, n, x, m)
        print(n - 1 - n_zero - n_dec)

def __starting_point():
    main()
__starting_point()

import numpy as np


k, q = list(map(int, input().split()))
d = np.array(list(map(int, input().split()))).astype(np.int64)
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = d % m
    quotient, rem = divmod(n - 1, k)
    rem_d_mod = d_mod[:rem]
    print((quotient * np.count_nonzero(d_mod) + np.count_nonzero(rem_d_mod)
          - (x % m + quotient * np.sum(d_mod) + np.sum(rem_d_mod)) // m))


import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), dtype=np.int)
for _ in range(q):
  n, x, m = map(int, input().split())
  quot = (n-1) // k
  rest = (n-1) % k
  dmod = d % m
  same = (k - np.count_nonzero(dmod)) * quot + rest - np.count_nonzero(dmod[:rest])
  a_last = x % m + dmod.sum() * quot + dmod[:rest].sum()
  beyond = a_last // m
  print(n - 1 - same - beyond)

import numpy as np


k, q = list(map(int, input().split()))
d = np.array(list(map(int, input().split()))).astype(np.int64)
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = d % m
    quotient, rem = divmod(n - 1, k)
    rem_d_mod = d_mod[:rem]
    print((quotient * np.count_nonzero(d_mod) + np.count_nonzero(rem_d_mod)
          - (x % m + quotient * d_mod.sum() + rem_d_mod.sum()) // m))


import numpy as np

k, q = list(map(int, input().split()))
d = np.array(input().split(), np.int64)
nxm = [list(map(int, input().split())) for _ in range(q)]

for n, x, m in nxm:
    dd = d % m

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

    print(ans)


import numpy as np


k, q = list(map(int, input().split()))
d = np.array(list(map(int, input().split()))).astype(np.int64)
queries = [tuple(map(int, input().split())) for _ in range(q)]

for n, x, m in queries:
    d_mod = d % m
    quotient, rem = divmod(n - 1, k)
    rem_d_mod = d_mod[:rem]
    print((n - 1 - (x % m + quotient * np.sum(d_mod) + np.sum(rem_d_mod)) // m
          - quotient * np.count_nonzero(d_mod == 0) - np.count_nonzero(rem_d_mod == 0)))