Buggy python submission (verdict: Time Limit Exceeded):
import sys

stdin = sys.stdin

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

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
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)


Fixed submission:
import sys

stdin = sys.stdin

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

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
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

stdin = sys.stdin

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

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

# K, Q = 2, 1000
# d = [1, 2]

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]


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
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        if l[i] < l[i+1]:
            turn += 1
    my = turn*m - l[-1]
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)


Fixed submission:
import sys

stdin = sys.stdin

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

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
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import sys

stdin = sys.stdin

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

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

# K, Q = 2, 1000
# d = [1, 2]

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]


import math
# count ax < k (mod p), 0 <= x < n
def countle(l, r, a, n, p):
    if l == r:
        return 0
    if n == 0:
        return 0

    a %= p

    # naive = 0
    # ans = 0
    # for i in range(n):
    #     x = a*i%p
    #     if l < r:
    #         if l <= x and x < r:
    #             ans += 1
    #     else:
    #         if x < r or l <= x:
    #             ans += 1

    s = min(n, int(math.sqrt(n)))
    # s = int(math.sqrt(n))
    comb = []
    q = 0
    for i in range(s):
        comb.append(q)
        q += a
        if q >= p:
            q -= p
    comb.sort()
    # print(p, comb)

    ll, rr = l, r
    ret = 0
    b = a * s % p
    for u in range(n//s):
        num = bisect.bisect_left(comb, r) - bisect.bisect_left(comb, l)
        if r < l:
            num += s
        ret += num
        # print(comb, l, r, num)

        l -= b
        r -= b
        if l < 0:
            l += p
        if r < 0:
            r += p

    if ll < rr:
        t = a*(n//s*s) % p
        for i in range(n//s*s, n):
            if ll <= t < rr:
                ret += 1
            t += a
            if t >= p:
                t -= p
    else:
        t = a*(n//s*s) % p
        for i in range(n // s * s, n):
            if t < rr or ll <= t:
                ret += 1
            t += a
            if t >= p:
                t -= p
    # print(ret, ans)
    # assert ret == ans
    return ret

# 2 3 5 7
# 0 2 3 5: 3
# 2 4 5 0: 2
# 4 6 0 2: 2
# 6 1 2 4

# a+k < b+k (mod p)
# a < bなら、k in [-a,p-1-b]
# a > bなら、k in [p-a, p-1-b]
# [-a,-1-b][-b, ...]
# a = bなら無
for z in range(Q):
    n, x, m = na()
    # n, x, m = 10+z, 1+z, 5+z

    # 36, 27, 31

    # 32, 33, 26

    # d0 = x
    # ex = 0
    # for i in range(n-1):
    #     d1 = d0 + d[i%K]
    #     if d0 % m < d1 % m:
    #         ex += 1
    #     d0 = d1

    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
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        # if m-l[i+1] > m-1-l[i]
        if l[i] < l[i+1]:
            turn += 1
    last = m-1-l[-1]
    if 0 == (last+1) % m:
        turn += 1
    # 0 3 6 ... 48 31
    # 0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48
    # % 31 0 <=  <= 2
    # print(ans, turn, last, -x%m, (-x+last+1)%m, l[-1], n//K)
    le = countle(-x%m, (-x+last+1)%m, l[-1], n//K, m)
    # print(le)
    ans += le*turn + (n//K-le)*(turn-1)
    print(ans)
    # assert ans == ex

    # x = turn - (start > last ? 1 : 0)


Fixed submission:
import sys

stdin = sys.stdin

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

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
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import sys

stdin = sys.stdin

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

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

# K, Q = 2, 1000
# d = [1, 2]

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]


import math
# count ax < k (mod p), 0 <= x < n
def countle(l, r, a, n, p):
    if l == r:
        return 0
    if n == 0:
        return 0

    a %= p

    # naive = 0
    # ans = 0
    # for i in range(n):
    #     x = a*i%p
    #     if l < r:
    #         if l <= x and x < r:
    #             ans += 1
    #     else:
    #         if x < r or l <= x:
    #             ans += 1

    s = min(n, int(math.sqrt(n)*4))
    # s = int(math.sqrt(n))
    comb = []
    q = 0
    for i in range(s):
        comb.append(q)
        q += a
        if q >= p:
            q -= p
    comb.sort()
    # print(p, comb)

    ll, rr = l, r
    ret = 0
    b = a * s % p
    for u in range(n//s):
        num = bisect.bisect_left(comb, r) - bisect.bisect_left(comb, l)
        if r < l:
            num += s
        ret += num
        # print(comb, l, r, num)

        l -= b
        r -= b
        if l < 0:
            l += p
        if r < 0:
            r += p

    if ll < rr:
        t = a*(n//s*s) % p
        for i in range(n//s*s, n):
            if ll <= t < rr:
                ret += 1
            t += a
            if t >= p:
                t -= p
    else:
        t = a*(n//s*s) % p
        for i in range(n // s * s, n):
            if t < rr or ll <= t:
                ret += 1
            t += a
            if t >= p:
                t -= p
    # print(ret, ans)
    # assert ret == ans
    return ret

# 2 3 5 7
# 0 2 3 5: 3
# 2 4 5 0: 2
# 4 6 0 2: 2
# 6 1 2 4

# a+k < b+k (mod p)
# a < bなら、k in [-a,p-1-b]
# a > bなら、k in [p-a, p-1-b]
# [-a,-1-b][-b, ...]
# a = bなら無
for z in range(Q):
    n, x, m = na()
    # n, x, m = 10+z, 1+z, 5+z

    # 36, 27, 31

    # 32, 33, 26

    # d0 = x
    # ex = 0
    # for i in range(n-1):
    #     d1 = d0 + d[i%K]
    #     if d0 % m < d1 % m:
    #         ex += 1
    #     d0 = d1

    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
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        # if m-l[i+1] > m-1-l[i]
        if l[i] < l[i+1]:
            turn += 1
    last = m-1-l[-1]
    if 0 == (last+1) % m:
        turn += 1
    # 0 3 6 ... 48 31
    # 0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48
    # % 31 0 <=  <= 2
    # print(ans, turn, last, -x%m, (-x+last+1)%m, l[-1], n//K)
    le = countle(-x%m, (-x+last+1)%m, l[-1], n//K, m)
    # print(le)
    ans += le*turn + (n//K-le)*(turn-1)
    print(ans)
    # assert ans == ex

    # x = turn - (start > last ? 1 : 0)


Fixed submission:
import sys

stdin = sys.stdin

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

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
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Buggy python submission (verdict: Runtime Error):
import bisect
import sys

stdin = sys.stdin

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

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

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]

import math
# count ax < k (mod p), 0 <= x < n
def countle(l, r, a, n, p):
    if l == r:
        return 0
    s = min(n, int(math.sqrt(n)*3))
    # s = int(math.sqrt(n))
    comb = [a*i % p for i in range(s)]
    comb.sort()

    ret = 0
    b = -a * s % p
    for u in range(n//s):
        # print(u, l, r)
        num = bisect.bisect_left(comb, r) - bisect.bisect_left(comb, l)
        if r < l:
            num += s
        ret += num

        l -= b
        r -= b
        if l < 0:
            l += p
        if r < 0:
            r += p

    if l < r:
        for i in range(n//s*s, n):
            if l <= a * i % p < r:
                ret += 1
    else:
        for i in range(n // s * s, n):
            if a * i % p < r or l <= a * i % p:
                ret += 1
    return ret

# 2 3 5 7
# 0 2 3 5: 3
# 2 4 5 0: 2
# 4 6 0 2: 2
# 6 1 2 4

# a+k < b+k (mod p)
# a < bなら、k in [-a,p-1-b]
# a > bなら、k in [p-a, p-1-b]
# [-a,-1-b][-b, ...]
# a = bなら無
for z in range(Q):
    n, x, m = na()

    # d0 = x
    # ex = 0
    # for i in range(n-1):
    #     d1 = d0 + d[i%K]
    #     if d0 % m < d1 % m:
    #         ex += 1
    #     d0 = d1

    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
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        # if m-l[i+1] > m-1-l[i]
        if l[i] < l[i+1]:
            turn += 1
    last = m-1-l[-1]
    if x == (x+last+1) % m:
        turn += 1
    # print(ans, turn, last, -x%m, (-x+last+1)%m, l[-1], n//K)
    le = countle(-x%m, (-x+last+1)%m, l[-1], n//K, m)
    # print(le)
    ans += le*turn + (n//K-le)*(turn-1)
    print(ans)
    # assert ans == ex

    # x = turn - (start > last ? 1 : 0)


Fixed submission:
import sys

stdin = sys.stdin

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

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
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)