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

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

K, Q = map(int, input().split())
D = list(map(int, input().split()))
NXM = [list(map(int, input().split())) for _ in range(Q)]

for N, X, M in NXM:
    E = [d % M for d in D]
    cnt0 = 0
    tmp0 = 0
    for e in E:
        if e > 0:
            cnt0 += 1
            tmp0 += e
    cnt = ((N - 1) // K) * cnt0
    tmp = ((N - 1) // K) * tmp0
    for i in range((N - 1) % K):
        if E[i] > 0:
            cnt += 1
        tmp += E[i]
    tmp += X % M
    print(cnt - tmp // M)

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

def solve():
    n, x, m = map(int, input().split())
    ans = 0
    rn = (n - 1) % k
    f = x % m
    for i in range(k):
        if d[i] % m == 0:
            continue
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        ans += c
        f += c * (d[i] % m)
    ans -= f // m
    print(ans)

for _ in range(q):
    solve()

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

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

def sum_count(A):
    S=0
    C=0
    for a in A:
        if a==0:
            C+=1
        else:
            S+=a
    return S,C

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

    D2=[d%m for d in  D]
    S,D0=sum_count(D2)
    R=(n-1)//k
    ANS=R*(k-D0) - (R*S+x%m)//m 
    x2=(x+S*R)%m
    rest=n-R*k-1
    S2,DR0=sum_count(D2[:rest])
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)

Solution (Python):

import sys
from itertools import accumulate
def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        count = [0]*k
        D = [0]*k
        c = 0
        for i in range(k):
            D[i] = d[i]%M
            if D[i] == 0:
                c += 1
            count[i] = c
        accum = list(accumulate(D))
        SUMD = accum[-1]
        COUNTD = count[-1]

        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + accum[(N-1)%k-1]
            equal_count = COUNTD*((N-1)//k)+count[(N-1)%k-1]
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    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):
k,q=map(int,input().split())
d=list(map(int,input().split()))
n=[0 for i in range(q)]
x=[0 for i in range(q)]
m=[0 for i in range(q)]
for i in range(0,q):
    n[i],x[i],m[i]=map(int,input().split())
x=[x[i]%m[i] for i in range(0,q)]
S=sum(d)
for i in range(0,q):
    p=[d[j]%m[i] for j in range(0,k)]
    test=0
    subtest=0
    for j in range(0,k):
        if p[j]!=0:
            test+=1
    s=x[i]%m[i]+sum(p)*((n[i]-1)//k)+sum(p[j] for j in range(0,(n[i]-1)%k))
    for j in range(0,(n[i]-1)%k):
        if p[j]!=0:
            subtest+=1
    if s%m[i]==0:
        print(test*((n[i]-1)//k)+subtest-(s//m[i]))
    else:
        print(test*((n[i]-1)//k)+subtest-(s//m[i]))

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())
    ds = []
    sumd = 0
    r = 0
    for i, d in enumerate(D):
        tmp = -(-(n-1-i)//K)
        ds.append(d%m)
        sumd += (d%m)*tmp
        if d%m == 0:
            r += tmp

    r += (sumd+x)//m - x//m

    print(n-1-r)

Solution (Python):
from collections import *
from itertools import *
from bisect import *
import copy

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:
    dlst=[d%m for d in D]
    count0=[(dlst[0]==0 )* 1]

    lst=[dlst[0]]
    for i in range(1,k):
        lst.append(lst[i-1]+dlst[i])
        count0.append(count0[i-1]+1*(dlst[i]==0))

    num2=(n-1)//k * lst[-1] +  x
    a=(n-1)%k-1
    if a>=0:
        num2+=lst[a]
    
    num1=n-1-((n-1)//k)*count0[-1]-(num2//m-x//m)
    if a>=0:
        num1-=count0[a]
    print(num1)

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


for n, x, m in query:
    Dmod = [d % m for d in D]
    equal = (n - 1) // K * sum(d == 0 for d in Dmod) + sum(d == 0 for d in Dmod[:((n - 1) % K)])

    a0 = x
    an = x + sum(Dmod) * ((n - 1) // K) + sum(Dmod[:((n - 1) % K)])
    small = an // m - a0 // m

    ans = (n - 1) - equal - small
    print(ans)

Solution (Python):
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    t = X%M
    for i in range(K):
        t += ((D[i]-1) % M + 1) * ((N-i-2) // K + 1)
    print(N - 1 - t//M)

Solution (Python):
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    if N <= K + 1:
        A = [0] * N
        A[0] = X % M
        ans = 0
        for i in range(N-1):
            A[i+1] = (A[i] + D[i]) % M
            if A[i+1] > A[i]:
                ans += 1
        print(ans)
        continue
    ans = N - 1
    t = X%M
    for i in range(K):
        d = (D[i]-1) % M + 1
        a = (N-i-2) // K + 1
        t += d * a
    ans -= t // M
    print(ans)

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

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())
    ans=n-1
    dm=[el%m for el in d]
    loop=(n-1)//k
    rem=(n-1)%k
    eqcnt=0
    lscnt=0
    totsum=0
    remsum=0
    for i in range(k):
        totsum+=dm[i]
        if i<rem:
            remsum+=dm[i]
        if dm[i]==0:
            eqcnt+=1
            if i<rem:
                ans-=1
    ans-=eqcnt*loop
    lscnt+=totsum//m*loop+remsum//m
    lscnt+=(totsum%m*loop+remsum%m+x%m)//m
    ans-=lscnt
    print(ans)

Solution (Python):
import sys

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()
    for _ in range(q):
        n,x,m=MI()
        sall=spart=0
        zall=zpart=0
        for i,d in enumerate(dd):
            d%=m
            if i<(n-1)%k:
                spart+=d
                if d==0:zpart+=1
            sall+=d
            if d==0:zall+=1
        last=x%m+sall*((n-1)//k)+spart
        no=last//m
        print(n-1-no-zall*((n-1)//k)-zpart)

main()

Solution (Python):
import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def search(n, x, m, K, D):
    ini = x % m
    modD = [D[i] % m for i in range(K)]
    roop , rem = (n - 1) // K, (n - 1) % K
    last = ini
    equal = 0
    for i in range(K):
        if i < rem and rem > 0:
            if modD[i] == 0: equal += roop + 1
            else: last += (roop + 1) * modD[i]
        else:
            if modD[i] == 0: equal += roop
            else: last += roop * modD[i]
    up = (last // m) - (ini // m)
    return n - 1 - equal - up

def solve():
    input = sys.stdin.readline
    K, Q = map(int, input().split())
    D = [int(d) for d in input().split()]
    Ans = []
    for _ in range(Q):
        n, x, m = map(int, input().split())
        Ans.append(search(n, x, m, K, D))

    for i, a in enumerate(Ans): print(a)

    return 0

if __name__ == "__main__":
    solve()

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

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans


'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''




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

que = []
for i in range(q):
    que.append(list(map(int, input().split())))
    


dsum = [0]

for i in range(k):
    dsum.append(dsum[-1]+d[i])

    
for i in range(q):
    dr = [d[j]%que[i][2] for j in range(len(d))]
    
    drsum = [0 for i in range(k+1)]
    for j in range(k):
        drsum[j+1] = drsum[j] + dr[j]
    count0 = [0 for i in range(k+1)]
    for j in range(k):
        if(dr[j]==0):
            count0[j+1] = count0[j]+1
        else:
            count0[j+1] = count0[j]
            
    times = (que[i][0]-1) // k
    amari = (que[i][0]-1) % k
    
    
    
    
    
    total = que[i][1] + drsum[-1]*times + drsum[amari]
    num0 = count0[-1]*times + count0[amari]
    
    ans = total//que[i][2] - que[i][1]//que[i][2]
    ans = que[i][0] - ans - num0 - 1
    
    print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

K, Q = na()
d = na()

for z in range(Q):
    n, x, m = na()

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1

    lpre = 0
    turn = 0
    
    j = rem
    for i in range(K):
        cur = (lpre + d[j]) % m
        if lpre < cur:
            turn += 1
        lpre = cur
        j += 1
        if j == K:
            j = 0
    my = turn*m - lpre
    
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

K, Q = na()
d = na()

for z in range(Q):
    n, x, m = na()

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1

    lpre = 0
    turn = 0
    
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

k,q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n,x,mod = map(int, input().split())
    dd = [di%mod if di%mod else mod for di in d]
    a,b = divmod(n-1, k)
    tmp = x%mod + a*sum(dd) + sum(dd[:b])
    print(n-1-tmp//mod)

Solution (Python):

import sys
input = sys.stdin.readline

k, q = [int(item) for item in input().split()]
d = [int(item) for item in input().split()]
nxm = []
for _ in range(q):
    n, x, m = [int(item) for item in input().split()]
    nxm.append((n, x, m))

for n, x, m in nxm:
    n -= 1
    newd = []
    is_zero = []
    sum_newd = 0
    for item in d:
        sum_newd += item % m
        newd.append(item % m)
        is_zero.append(item % m == 0)
    loop = n // k
    rest = n % k
    total = loop * (sum_newd) + (x % m) 
    zeros = loop * sum(is_zero)
    total += sum(newd[:rest])
    zeros += sum(is_zero[:rest])
    rollover = total // m
    ret = n - rollover - zeros
    print(ret)

Solution (Python):
import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    acc = list(accumulate(eee))
    zero = [int(e == 0) for e in eee]
    zero_acc = list(accumulate(zero))
    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
    
    
    
    
    
    return n - 1 - dame - tot_zero


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))

Solution (Python):
import sys
input = sys.stdin.readline
k, q = map(int,input().split())
D = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
    n = A[i][0]
    x = A[i][1]
    m = A[i][2]
    ans = 0
    B = [x%m]
    BP = [0] * (k+1)
    n -= 1
    for j in range(k):
        B.append((B[-1] + D[j]) % m)
    ans0 = 0
    for j in range(len(B)-1):
        if B[j+1] > B[j]:
            BP[j+1] = 1
            ans0 += 1
    
    if B[-1] != B[0]:
        if B[-1] > B[0]:
            ans1 = [ans0-1, ans0]
        elif B[-1] < B[0]:
            
            ans1 = [ans0, ans0+1]
        d = (B[-1] - B[0]) % m
        kn = n // k
        c = (B[0] + d * kn) % m
        sag = (B[0] + d * kn) // m
        
        ans = ans1[0] * sag + ans1[1] * (kn-sag)
        
        for ii in range(n%k):
            cm = c
            
            c += D[ii]
            if c >= m:
                c %= m
            
            if c>cm:
                ans += 1    
        print(ans)
        
    else:
        
        print(ans0 * (n//k) + sum(BP[:n%k+1]))

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

Solution (Python):
k, q = list(map(int, input().split()))
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for _ in range(q)]

D = [[0] * 2 for _ in range(k)]
for i in range(q):
  n, x, m = nxm[i]
  D[-1] = [0, 0]
  D[0][0] = d[0] % m
  D[0][1] = 0

  for j in range(k):
    D[j][0] = (D[j - 1][0] + d[j] % m)
    D[j][1] = D[j - 1][1]
    if D[j - 1][0] != D[j][0]:
      D[j][1] += 1

  N, M = divmod(n - 1, k)

  ans = N * D[-1][1]
  t = N * D[-1][0] + (x % m)
  ans -= t // m
  t = t % m
  if M != 0:
    ans += D[M - 1][1]
    t += D[M - 1][0]
    ans -= t // m
  
  print(ans)

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

def solve(n,x,m):
    S=[0]*(k+1)
    cnt_z=[0]*(k+1)
    for i in range(k):
        a=d[i]%m
        S[i+1]=S[i]+a
        cnt_z[i+1]=cnt_z[i]
        if a==0:
            cnt_z[i+1]+=1
    pp=(n-1)//k
    r=(n-1)%k
    
    s=x+S[-1]*pp+S[r]
    
    ans=(n-1)-s//m-cnt_z[-1]*pp-cnt_z[r]
    print(ans)
    
    


for i in range(q):
    n,x,m=map(int,input().split())
    x%=m
    solve(n,x,m)

Solution (Python):
def process(k, d, n, x, m):
  d_mod = [di % m for di in d]
  sum_d_mod = sum(d_mod)
  inc_times1 = len([d_mod_i for d_mod_i in d_mod if d_mod_i])
  rem_d_mod = sum(d_mod[0:(n-1)%k])
  inc_times2 = len([d_mod_i for d_mod_i in d_mod[0:(n-1)%k] if d_mod_i])
  last = x + sum_d_mod * ((n-1) // k) + rem_d_mod
  first = x
  ans = inc_times1 * ((n-1) // k) + inc_times2
  ans -= last // m - first // m
  print(ans)


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())
    process(k, d, n, x, m)



if __name__ == "__main__" :
  main()

Solution (Python):
k,q = map(int,input().split())
d = list(map(int,input().split()))
al = []
for i in range(q):
    n,x,m = map(int,input().split())
    pd = []
    count = 0
    for j in range(k):
        pd.append(d[j]%m)
        if d[j]%m == 0:
            count += 1
    a = sum(pd)
    ans = x%m
    ans += a*((n-1)//k)
    
    c = 0
    for j in range((n-1)%k):
        ans += pd[j]
        if pd[j] == 0:
            c += 1
    al.append(n-1-(ans//m)-count*((n-1)//k)-c)
for i in range(q):
    print(al[i])

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

def main():
    k,q=map(int,input().split())
    D=tuple(map(int,input().split()))
    for _ in range(q):
        n,x,m=map(int,input().split())
        x%=m
        Di=[]
        zero=0
        for d in D:
            tmp=d%m
            if tmp==0:
                zero+=1
            Di.append(tmp)
        s=sum(Di)
        cycles=(n-1)//k
        cycle_sum=cycles*s
        remain=(n-1)%k
        
        last=x+cycle_sum
        for i in range(remain):
            last+=Di[i]
        
        q=n-1
        q-=zero*cycles
        for i in range(remain):
            if Di[i]==0:
                q-=1
        q-=last//m
        print(q)
    
if __name__=='__main__':
    main()

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

K, Q = map(int, readline().split())

D = list(map(int, readline().split()))

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    x%= mod
    D2 = [d%mod for d in D]
    res = 0
    cnt = 0
    zero = 0
    for d2 in D2:
        res += d2
        if res > mod:
            cnt += 1
            res -= mod
        if not d2:
            zero += 1
    
    loop =  ((n-1)//K)
    minus = loop*cnt
    zero *= loop
    res2 = 0
    for i in range((n-1)%K):
        res2 += D2[i]
        if not D2[i]:
            zero += 1
        if res2 > mod:
            res2 -= mod
            minus += 1
    minus += (x%mod + loop*res + res2)//mod
    Ans[q] = n-1 - zero - minus
print('\n'.join(map(str, Ans)))

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

def query(n,x,m):
    res = n-1
    n -= 1
    x %= m
    s1 = 0
    t1 = 0
    for i in range(k):
        s1 += d[i]%m
        if d[i]%m==0:
            t1 += 1
    s2 = 0
    t2 = 0
    for i in range(n%k):
        s2 += d[i]%m
        if d[i]%m==0:
            t2 += 1
    x += s1*(n//k)+s2
    res -= x//m
    res -= t1*(n//k)+t2
    return res

for i in range(q):
    n,x,m = map(int,input().split())
    print(query(n,x,m))

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

K, Q = map(int, readline().split())

D = list(map(int, readline().split()))

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    x%= mod
    D2 = [d%mod for d in D]
    res = 0
    cnt = 0
    zero = 0
    for d2 in D2:
        res += d2
        if res > mod:
            cnt += 1
            res -= mod
        if not d2:
            zero += 1
    
    loop =  ((n-1)//K)
    minus = loop*cnt
    zero *= loop
    res2 = 0
    for i in range((n-1)%K):
        res2 += D2[i]
        if not D2[i]:
            zero += 1
        if res > mod:
            res -= mod
            minus += 1
    minus += (x%mod + loop*res + res2)//mod
    Ans[q] = n-1 - zero - minus
print('\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())
  x %= m
  dm = []
  for dx in d:
    dm.append((dx-1)%m+1)
  sumd = (n-1)//k * sum(dm) + sum(dm[:(n-1)%k])
  ans = n - 1 - (x+sumd)//m + (x)//m
  
  
  
  print(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())
    d = [0]*K;zeroes = [0]*(K+1);sum = [0]*(K+1)
    for i in range(K):d[i] = d_[i] % m
    for i in range(K):zeroes[i+1] = zeroes[i] + (d[i] == 0)
    for i in range(K):sum[i+1] = sum[i] + d[i]
    
    s = (n-1)//K*sum[K] + sum[(n-1)%K]
    s += x%m
    
    num0 = (n-1)//K*zeroes[K] + zeroes[(n-1)%K]
    print(n-1-s//m-num0)

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


import numpy as np

stdin = open(0)


K, Q = map(int, stdin.readline().split())
D = np.array(stdin.readline().split(), np.int64)
m = map(int, stdin.read().split())
query = tuple(zip(m, m, m))



def solve(n, x, m):
    Dm = D % m
    Dcum = np.cumsum(Dm)
    q, r = divmod(n - 1, K)
    last = x + Dcum[-1] * q
    if r:
        last += Dcum[r - 1]
    is_zero = np.cumsum(Dm == 0).astype(np.int64)
    stable = is_zero[-1] * q
    if r:
        stable += is_zero[r - 1]
    decr = (last // m) - (x // m)
    return n - 1 - stable - decr



for n, x, m in query:
    print(solve(n, x, m))