Problem:
 Score : 600 points    Problem 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) .      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 1 3 1
3 1 4
5 3 2      Sample Output 1 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 .       Sample Input 2 7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12      Sample Output 2 224489796
214285714
559523809

Solution (Python):
k, q = map(int, input().split())
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for i in range(q)]
for n, x, m in nxm:
    prev = x
    ans = 0
    cur = 0
    for i in range(k):
        prev += (d[i] % m) * ((n + k - i  - 2) // k)
        if d[i] % m == 0:
            cur += ((n + k - i  - 2) // k)
    print(n - prev // m + x // m - cur - 1)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k, q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(q):
        n, x, m = map(int, input().split())
        b = x
        for i in range(k):
            s = (n - 2 - i) // k + 1
            t = D[i] % m
            if t == 0:
                t = m
            b += s * t
        print(n - 1 - (b // m - x // m))
resolve()

Solution (Python):
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
        
        ans -= t * cnt_D0
        

        progress = sum_D * t
        x1 = x%m + progress
        for i in range(rem):
            d = D_mod[i]
            if d == 0:
                ans -= 1
            x1 += d
        
        

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

Solution (Python):
def main():
    K, Q = list(map(int, input().split()))
    D = list(map(int, input().split()))
    query_list = [list(map(int, input().split())) for _ in range(Q)]
    ans = [0 for _ in range(Q)]
    for q, query in enumerate(query_list):
        N, X, M = query
        
        mod_d = [d % M for d in D]
        
        cnt_no_change = 0
        for i, d in enumerate(mod_d):
            
            if d != 0:
                continue
            cnt = (N - 2) // K
            if i <= (N - 2) % K:
                cnt += 1
            cnt_no_change += cnt
        
        initial_a = X
        final_a = initial_a  
        for i, d in enumerate(mod_d):
            cnt = (N - 2) // K
            if i <= (N - 2) % K:
                cnt += 1
            final_a += cnt * d
        cnt_decrease = final_a // M - initial_a // M
        ans[q] = N - 1 - cnt_no_change - cnt_decrease
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):
import math

k, q = map(int, input().split())
_d = list(map(int, input().split()))
for _ in range(q):
    n, x, m = map(int, input().split())
    d = map(lambda xx: xx % m, _d)
    ans = 0
    s = 0
    for i, di in enumerate(d):
        if di == 0:
            ans += math.ceil((n - i - 1) / k)
        else:
            s += di * math.ceil((n - i - 1) / k)
    ans += (s + x) // m - x // m
    print(n - 1 - ans)

Solution (Python):
import sys
def LI():
    return list(map(int,sys.stdin.readline().rstrip().split()))  

k,q = LI()
d = LI()

from itertools import accumulate

for _ in range(q):
    n,x,m = LI()
    e = [0] + [d[i] % m for i in range(k)]
    f = list(accumulate(e))
    g = [0] + [d[i] % m == 0 for i in range(k)]
    h = list(accumulate(g))
    p,r = divmod(n - 1,k)
    print(n - 1 - p*h[k] - h[r] - (p*f[k] + f[r] + x % m) // m)

Solution (Python):
import sys
def LI():
    return list(map(int,sys.stdin.readline().rstrip().split()))  

k,q = LI()
d = LI()

from itertools import accumulate

for _ in range(q):
    n,x,m = LI()
    e = [0] + [d[i] % m for i in range(k)]
    f = list(accumulate(e))
    g = [0] + [d[i] % m == 0 for i in range(k)]
    h = list(accumulate(g))
    p = (n-1) // k
    r = (n-1) % k
    print(n - 1 - p*h[k] - h[r] - (p*f[k] + f[r] + x % m) // m)

Solution (Python):
import sys
input = sys.stdin.readline

k, q = map(int, input().split())
D = tuple(map(int, input().split()))
for _ in range(q):
  n, x, m = map(int, input().split())
  E = tuple(d%m for d in D)
  temp = n-1
  b = x
  for i, e in enumerate(E, 1):
    c = -(-(n-i)//k)
    if e == 0:
      temp -= c
    b += e*c
  temp -= b//m - x//m
  print(temp)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

import numpy as np
def resolve():
    K, Q = map(int, inp().split())
    D = np.array(inp().split(), dtype=np.int64)
    nxm = [list(map(int, inp().split())) for _ in range(Q)]

    for n, x, m in nxm:
        
        
        E = D % m
        acc_E = np.cumsum(E)

        
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        
        zero_acc = np.cumsum(E == 0).astype(np.int64)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    resolve()

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    k, q = inp[:2]
    ddd = inp[2:k + 2]
    nnn = inp[k + 2::3]
    xxx = inp[k + 3::3]
    mmm = inp[k + 4::3]
    buf = []
    for n, x, m in zip(nnn, xxx, mmm):
        eee = ddd % m
        acc = np.cumsum(eee)
        zero_acc = np.cumsum(eee == 0)
        loop, rem = divmod(n - 1, k)
        tot = x % m + acc[-1] * loop
        tot_zero = zero_acc[-1] * loop
        if rem > 0:
            tot += acc[rem - 1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        buf.append(n - 1 - dame - tot_zero)
    return buf


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def sub(n,x,m):
    X = 0
    init = x%m
    x%=m
    n -= 1
    if n<=k:
        for i in range(n):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        ans = X
    else:
        for i in range(k):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        diff = (x-init)
        ans = (n//k) * X - (init + (diff*(n//k))) // m
        nn = n-(n//k)*k
        xx = (init + (diff*(n//k))) % m


        for i in range(nn):
            if xx<(xx+d[i])%m:
                ans += 1
            xx = (xx+d[i])%m
    return ans


ans = [None]*q
for i in range(q):
    n,x,m = map(int, input().split())
    ans[i] = sub(n,x,m)
write("\n".join(map(str, ans)))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def sub(n,x,m):
    X = 0
    init = x%m
    x%=m
    if n<=k:
        for i in range(n-1):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        ans = X
    else:
        for i in range(k):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        diff = (x-init)
        ans = ((n-1)//k) * X - (init + (diff*((n-1)//k))) // m
        nn = n-((n-1)//k)*k
        xx = (init + (diff*((n-1)//k))) % m


        for i in range(nn-1):
            if xx<(xx+d[i])%m:
                ans += 1
            xx = (xx+d[i])%m
    return ans


ans = [None]*q
for i in range(q):
    n,x,m = map(int, input().split())
    ans[i] = sub(n,x,m)
write("\n".join(map(str, ans)))

Solution (Python):
k, q = map(int, input().split())
d = list(map(int, input().split()))
for _ in range(q):
    n, x, m = map(int, input().split())
    tmp = x
    a = list(map(lambda y: y % m, d))
    c = 0
    s = 0
    c2 = 0
    s2 = 0
    for x in a:
        if x == 0:
            c += 1
        s += x
    for x in a[:(n - 1) % k]:
        if x == 0:
            c2 += 1
        s2 += x
    t = s * ((n - 1) // k) + s2 + tmp % m
    ans = n - 1 - t // m - c * ((n - 1) // k) - c2
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


k, q = map(int, input().split())
d = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(q)]

for n, x, mod in info:
    d_mod = [d[i] % mod for i in range(k)]
    laps, rem = divmod(n - 1, k)
    start = x % mod
    end = start + sum(d_mod) * laps + sum(d_mod[0:rem])
    ans = n - (end // mod - start // mod + 1)

    
    is0 = [d_mod[i] == 0 for i in range(k)]
    cnt0 = sum(is0) * laps + sum(is0[0:rem])
    print(ans - cnt0)

Solution (Python):

import sys
INF = float("inf")


def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):

    for i in range(q):
        dmod = [v % m[i] for v in d]
        zero = 0
        c, p = divmod(n[i]-1, k)
        last = x[i]
        
        
        for j in range(k):
            if j < p:
                last += (c+1)*dmod[j]
                if dmod[j] == 0:
                    zero += c+1
            else:
                last += c*dmod[j]
                if dmod[j] == 0:
                    zero += c
        print(n[i]-1-(zero + (last//m[i] - x[i]//m[i])))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    k = int(next(tokens))  
    q = int(next(tokens))  
    d = [int(next(tokens)) for _ in range(k - 1 - 0 + 1)]  
    n = [int()] * (q)  
    x = [int()] * (q)  
    m = [int()] * (q)  
    for i in range(q):
        n[i] = int(next(tokens))
        x[i] = int(next(tokens))
        m[i] = int(next(tokens))
    solve(k, q, d, n, x, m)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys
input = sys.stdin.buffer.readline

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

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

for _ in range(q):
    n, x, m = map(int, input().split())
    tmp = x % m
    d_mod = (d-1) % m + 1 
    d_cumsummod = np.cumsum(d_mod)
    d_cumsummod = np.concatenate((np.zeros(1, np.int64), d_cumsummod))
    d_q, d_r = divmod(n-1, k)
    tmp += (d_q * d_cumsummod[-1] + d_cumsummod[d_r])
    print((n-1) - tmp // m)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	K, Q = getlist()
	D = getlist()
	for _ in range(Q):
		N, X, M = getlist()
		X %= M
		d = [0] * K
		zeroCount = 0
		for i in range(K):
			var = D[i] % M
			d[i] = var
			if var == 0:
				zeroCount += 1
		Dsum = sum(d)
		p = int((N - 1) // K)
		q = (N - 1) % K
		An = X + Dsum * p
		
		
		
		zero = 0
		for i in range(q):
			An += d[i]
			if d[i] == 0:
				zero += 1

		
		
		
		ans = N - 1 - (zeroCount * p + zero) - (int(An // M) - int(X  // M))
		print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        kmod = (n-1)%k
        kdiv = (n-1)//k
        cnt = 0; cntm = 0
        for i in range(k):
            cnt += dmodm[i] == 0
            cntm += (dmodm[i] == 0 and i < kmod)
        
        
        dmodcum = list(itertools.accumulate(dmodm))
        
        p0 = cnt * kdiv + cntm
        an = x + (kmod != 0) * dmodcum[kmod-1] + dmodcum.pop() * kdiv
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
k,q = map(int,input().split())
dbase = list(map(int,input().split()))
for _ in range(q):
  n,x,m = map(int,input().split())
  x %= m
  dls = [d%m for d in dbase]
  q,r = divmod(n-1,k)
  end = x
  minus = 0
  for i in range(k):
    if i < r:
      end += dls[i]*(q+1)
      if dls[i] == 0:
        minus += q+1
    else:
      end += dls[i]*q
      if dls[i] == 0:
        minus += q
  minus += end//m
  print(n-minus-1)

Solution (Python):
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)

Solution (Python):
import math








import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))

    for qi in range(q):
        n, x, m = map(int, input().split())
        last = x
        eq = 0
        for i in range(k):
            num = (n-1)//k
            if (n-1) % k >= i+1:
                num += 1  
            last += (d[i] % m)*num
            if d[i] % m == 0:
                eq += num

        ans = (n-1)-(last//m-x//m)-eq
        print(ans)


resolve()

Solution (Python):
def main():
    import numpy as np
    k, q = 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()

Solution (Python):
def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()

Solution (Python):

import sys

sysread = sys.stdin.readline


sys.setrecursionlimit(10**7)


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

if __name__ == "__main__":
    run()

Solution (Python):
import math
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def ceil(a, b):
    return (a+b-1)//b


def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for i in range(q):
        n, x, m = map(int, input().split())
        last = x
        eq = 0
        for j in range(k):
            num = ceil((n-1-j), k)
            last += (d[j] % m)*num
            if d[j] % m == 0:
                eq += num
        ans = (n-1) - (last//m - x//m) - eq
        print(ans)


main()

Solution (Python):
import numpy as np
k, q = map(int, input().split())
d = np.array(list(map(int, input().split())))
for _ in range(q):
    n, x, m = 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)

Solution (Python):
import math


mod=10**9+7

k,q=map(int,raw_input().split())
d=map(int,raw_input().split())
while q:
	q-=1
	n,x,m=map(int,raw_input().split())
	ans=0
	di=(n-1)/k
	cnt=x%m
	left=n-(di*k +1)
	xd=[]
	for i in range(k):
		xd.append(d[i]%m)
	
	for i in range(k):
		lol=0
		if i<left:
			lol=1
		if(xd[i]==0):
			ans+=(lol+di)
		else:
			cnt+=(xd[i]*(lol+di))
	ans+=(cnt/m)
	print n-1-ans

Solution (Python):
K,Q = map(int,input().split())
D = list(map(int,input().split()))
NXM = [tuple(map(int,input().split())) for i in range(Q)]

for N,X,M in NXM:
    ds = [d%M for d in D]
    a,b = divmod(N-1,K)
    s = 0
    z = 0
    for i,d in enumerate(ds):
        if i==b:
            sb = s
            zb = z
        if d==0:
            z += 1
        s += d
    x = (X + s*a + sb)//M - X//M
    y = z*a + zb
    print(N-1-x-y)

Solution (Python):
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)
if __name__ == '__main__':
  main()

Solution (Python):
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)

Solution (Python):
k,q=map(int,input().split())
d=list(map(int,input().split()))

for _ in range(q):
    n,x,m = map(int,input().split())
    li = [0]*k
    tmp = 0
    for i in range(k):
        li[i] = d[i]%m
    cnt = x % m
    n -= 1
    for i in range(k):
        cnt += ( n//k + (n%k > i) ) * li[i]
        if li[i] == 0:
            tmp += ( n//k + (n%k > i) )
    print(n-cnt//m - tmp)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k,q = LI()
    d = LI()
    aa = [LI() for _ in range(q)]

    def f(n,x,m):
        e = [c%m for c in d]
        n -= 1
        s = sum(e)
        t = s * (n//k) + sum(e[:n%k])
        xt = x + t
        z = [1 if c == 0 else 0 for c in e]
        zs = sum(z) * (n//k) + sum(z[:n%k])
        
        return n - (xt//m - x//m) - zs

    r = [f(n,x,m) for n,x,m in aa]
    return JA(r, "\n")


print(main())

Solution (Python):
import numpy as np


k, q = 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)

Solution (Python):
import numpy as np


k, q = 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)

Solution (Python):
import numpy as np


k, q = 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))

Solution (Python):
import numpy as np


k, q = 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))

Solution (Python):
import sys
input = sys.stdin.readline

k, q = map(int, input().split())
d = tuple(map(int, input().split()))


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)

Solution (Python):
k, q = map(int, input().split())
d = tuple(map(int, input().split()))


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    
    for i in range(k):
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[k,q]=i2()
d=i2()
for i in range(q):
  [n,x,m]=i2()
  di=[]
  dz=[]
  for i in d:
    di.append(i%m)
    if i%m==0:
       dz.append(1)
    else:
       dz.append(0)
  x=((n-1)//k)*sum(di[:k])+x%m
  if (n-1)%k:
    x+=sum(di[:(n-1)%k])
  ans=n-1-x//m-((n-1)//k)*sum(dz[:k])
  if (n-1)%k:
   ans-=sum(dz[:(n-1)%k])
  print(ans)

Solution (Python):
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 = map(int, input().split())
    d_list = list(map(int, input().split()))
    query_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]


if __name__ == "__main__":
    
    main()

Solution (Python):
import sys
input = sys.stdin.readline

k, q = map(int, input().split())
d_ = list(map(int, input().split()))

for _ in range(q):
    n, x, m = map(int, input().split())
    d = [di%m for di in d_]
    ans = n-1
    zero_acc = [0]
    sum_acc = [0]
    
    for di in d:
        zero_acc.append(zero_acc[-1]+(1 if di==0 else 0))
        sum_acc.append(sum_acc[-1]+di)
    
    s, a = divmod(n-1, k)
    ans -= s*zero_acc[-1]+zero_acc[a]
    last = x+s*sum_acc[-1]+sum_acc[a]
    ans -= last//m-x//m
    
    print(ans)

Solution (Python):
k, q = map(int, input().split())
d = [int(x) for x in input().split()]

for _ in range(q):
    n, x, m = map(int, input().split())
    z = 0
    last = x
    ans = 0

    for i in range(k):
        dnum = (n-1-i+(k-1))//k
        last += d[i]%m * dnum
        if d[i]%m == 0:
            z += dnum
        
    ans = (n-1) - (last//m - x//m) - z
    print(ans)

Solution (Python):


import sys

debug = False

def solve(ds, n, x, m):
    ds = [d % m for d in ds]

    nr_loop = (n - 1) // len(ds)
    lastloop_remaining = (n - 1) % len(ds)
    a_n = x
    cnt_zero = 0
    for i in range(0, len(ds)):
        dmod = ds[i] % m
        a_n += (dmod) * nr_loop
        if dmod == 0:
            cnt_zero += nr_loop
        if i < lastloop_remaining:
            a_n += dmod
            if dmod == 0:
                cnt_zero += 1
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_zero


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

Solution (Python):
k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) 
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: 
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: 
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)

Solution (Python):
import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) 
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: 
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: 
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    K, q = map(int, input().split())
    D_raw = list(map(int, input().split()))
    for _ in range(q):
        N, x, M = map(int, input().split())

        x %= M
        a = (N-1) % K
        b = (N-1) // K
        D = [0] * K
        zero_num = 0
        zero_num_2 = 0
        for i in range(K):
            d = D_raw[i]%M
            D[i] = d
            if not d:
                zero_num += 1
                if i < a:
                    zero_num_2 += 1
        ans = N - 1 - zero_num * b - zero_num_2 - (sum(D) * b + sum(D[:a]) + x) // M
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
k, q = map(int, input().split())
d = list(map(int, input().split()))
 
for _ in range(q):
	n, x, m = map(int, input().split())
 
	res = 0
	for i in range(k):
		a = d[i] % m
		if a == 0:
			a += m
		res += a * ((n - i -2)//k + 1)
	print( (n-1) - ((x+res)//m - x//m) )

Solution (Python):
k,q = map(int,input().split())
d = [int(i) for i in input().split()]

for i in range(q):
    n,x,m = map(int,input().split())
    cum = [0]*(k+1)
    cnt = [0]*(k+1)
    for i in range(k):
        cum[i] = cum[i-1]+d[i]%m
        cnt[i] = cnt[i-1]
        if d[i]%m == 0:
            cnt[i]+=1
    res = x%m+cum[k-1]*((n-1)//k)+cum[((n-1)%k)-1]
    s = res//m
    print(n-1-s-cnt[k-1]*((n-1)//k)-cnt[(n-1)%k-1])

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

k, q = map(int, input().split())
d = list(map(int, input().split()))
for _ in range(q):
    n, x, m = map(int, input().split())
    ans = n - 1
    s = x % m
    dm = [i % m for i in d]
    accum = list(accumulate(dm))
    count = [0] * k
    for i in range(k):
        if dm[i] == 0:
            count[i] += 1
    count = list(accumulate(count))

    s += accum[-1] * ((n-1) // k)
    ans -= count[-1] * ((n-1) // k)
    if (n-1) % k > 0:
        s += accum[(n-1) % k - 1]
        ans -= count[(n-1) % k - 1]
    ans -= s // m
    print(ans)