CodeEff/ECCO huggingface dataset:
# Original solution
N = int(eval(input()))
X = list(map(int, input().split()))
L = []
for i in range(N):
  L.append([X[i], i])
L.sort()
for i in range(N):
  if i < N // 2:
    L[i].append(L[N // 2][0])
  else:
    L[i].append(L[N // 2 - 1][0])
for i in range(N):
  L[i][0], L[i][1] = L[i][1], L[i][0]
L.sort()
for i in range(N):
  print((L[i][2]))

# Optimized solution
N = int(eval(input()))
X = list(map(int, input().split()))
L = [0 for _ in range(N)]
for i in range(N):
  X[i] = X[i] * N + i
X.sort()
d = N // 2
for i in range(N):
  if i < d:
    L[X[i]%N] = X[d] // N
  else:
    L[X[i]%N] = X[d-1] // N
for i in range(N):
  print((L[i]))
# Original solution
A, B, C, K = list(map(int, input().split()))

if A == B:
    print((0))
else:
    for _ in range(K):
        tmp_A = B + C
        tmp_B = A + C
        C = A + B
        A = tmp_A
        B = tmp_B
        if A - B >= 10 ** 18:
            print(Unfair)
            break
    else:
        print((A-B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))

if K % 2 == 1:
    print((B-A))
elif K % 2 == 0:
    print((A-B))
# Original solution
A, B, C, K = list(map(int, input().split()))

if K % 2 == 1:
    print((B-A))
elif K % 2 == 0:
    print((A-B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))

if K % 2 == 1:
    print((B-A))
elif K % 2 == 0:
    print((A-B))
else:
    print('Unfair')
# Original solution
def change(A,B,C):
    move=True
    a=A
    b=B
    c=C
    A=b+c
    B=a+c
    C=a+b
    if B-A==b-a:
        move=False
    return A,B,C,move
A,B,C,K=list(map(int,input().split()))
ans=A-B
for i in range(K):
    A,B,C,move=change(A,B,C)
    ans=A-B
    if abs(ans)>1000000000000000000:
        print("Unfair")
        break
    elif not(move):
        print(ans)
        break
else:
    print(ans)

# Optimized solution
A,B,C,K=list(map(int,input().split()))
if K%2==0:
    ans=A-B
else:
    ans=B-A
if ans>1000000000000000000:
    ans="Unfair"
print(ans)
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

A, B, C, K = mapint()
for _ in range(K):
    A, B, C = B+C, A+C, A+B
    if abs(A-B)>10**18:
        print('Unfair')
        break
    if A-B==0:
        print((0))
        break
else:
    print((A-B))

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

A, B, C, K = mapint()
if K%2==0:
    print((A-B))
else:
    print((B-A))
# Original solution
A, B, C, K = list(map(int, input().split()))

ans = A - B
if K%2==1:
    ans = -ans

if abs(ans) > 10**18:
    ans = "Unfair"

print(ans)

# Optimized solution
A, B, C, K = list(map(int, input().split()))

ans = A - B
if K%2==1:
    ans = -ans

print(ans)
# Original solution
a, b, c, k = list(map(int, input().split()))

limit = pow(10, 18)

ans = 0
unfair = False
for v in range(k):
    if a == b and b == c:
        break
    na = b + c
    nb = a + c
    nc = a + b
    a = na
    b = nb
    c = nc
ans = a - b
if abs(ans) > limit:
    print("Unfair")
else:
    print(ans)


# Optimized solution
a, b, c, k = list(map(int, input().split()))

if k % 2 == 0:
    print((a - b))
else:
    print((b - a))
# Original solution
a,b,c,k=list(map(int,input().split()))
if k%2==0:
  print((a-b))
else:
  print((b-a))

# Optimized solution
a,b,c,k = list(map(int, input().split()))
if k % 2:
  print((b - a))
else:
  print((a - b))
# Original solution
import copy
a,b,c,k = list(map(int,input().split()))

if a == b == c:
    print((0))
    exit()

cnt = 0
while True:
    if cnt >= k:
        print((a - b))
        break
    aa = copy.deepcopy(a)
    bb = copy.deepcopy(b)
    cc = copy.deepcopy(c)

    a = bb + cc
    b = aa+cc
    c = aa + bb
    cnt += 1
    if abs(a-b) >= 10**18:
        print('Unfair')
        break



# Optimized solution
a,b,c,k = list(map(int,input().split()))

x = abs(a-b)
if x > 10**18:
    print('Unfair')
else:
    if k % 2 == 0:
        print((a - b))
    else:
        print((b-a))
# Original solution
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    a,b,c,k = list(map(int,input().split()))
    high=a
    middle=b
    low=c
    count=0

    while count<k:
        if abs(high-middle) >10**18:
            print("Unfair")
            exit()
        elif a == b == c:
            print((0))
            exit()
        high = b+c
        middle = a+c
        low = a+b
        a=high
        b=middle
        c=low
        count+=1
    print((high-middle)) 
    

if __name__=="__main__":
    main()

# Optimized solution
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    a,b,c,k = list(map(int,input().split()))

    if abs(a-b)>10**18:
        print("Unfair")
    elif k % 2==0:
        print((a-b))
    else:
        print((b-a)) 

if __name__=="__main__":
    main()
# Original solution
s = input().rstrip().split()
a = int(s[0])
b = int(s[1])
c = int(s[2])
k = int(s[3])

for i in range(k):
  n_a = b+c
  n_b = a+c
  n_c = a+b
  a = n_a
  b = n_b
  c = n_c
  if(a == b and b == c ):
    break

d = a - b
if(abs(d) < 100000000):
  print((a-b))
else:
  print("Unfair")

# Optimized solution
s = input().rstrip().split()
a = int(s[0])
b = int(s[1])
c = int(s[2])
k = int(s[3])

ans = a - b

if(k%2==1):
  ans = -1 * ans

if(abs(ans) < 1000000000000000000):
  print(ans)
else:
  print("Unfair")
# Original solution
A, B, C, K = list(map(int, input().split()))
for _ in range(K):
  if A == B == C:
    break
  A, B, C = B + C, A + C, A + B
if abs(A - B) > 10 ** 18:
  print('Unfair')
else:
  print((A-B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))

o = B - A
e = A - B
if K % 2 == 0:
  r = e
else:
  r = o 
print(r)
# Original solution
A, B, C, K = list(map(int, input().split()))

for i in range(K):
    tmpA = B + C
    tmpB = A + C
    tmpC = A + B
    A = tmpA
    B = tmpB
    C = tmpC

    if A == B and B == C:
        break

if (A - B) >= 10**18:
    print("Unfair")
else:
    print((A - B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))

if K % 2 == 0:
    print((A - B))
else:
    print((B - A))
# Original solution
a, b, c, k = list(map(int, input().split()))
if k%2==0:
    if b-a < 10**18:
        print((a-b))
    else:
        print("Unfair")
else:
    if a-b < 10**18:
        print((b-a))
    else:
        print("Unfair")

# Optimized solution
a,b,_c,k=list(map(int,input().split()))
if k%2==0:print((a-b))
else:print((b-a))
# Original solution
#!/usr/bin/env python3

def main():
    A, B, C, K = list(map(int, open(0).read().split()))

    flag = True
    for i in range(0, K):
        if abs(A - B) > 10**18:
            print('Unfair')
            flag = False
            break
        elif A == B == C:
            print((0))
            flag = False
            break
        else:
            tmpA = B + C
            tmpB = A + C
            tmpC = A + B
            A = tmpA
            B = tmpB
            C = tmpC
    if flag:
        print((A - B))


main()

# Optimized solution
#!/usr/bin/env python3

def main():
    A, B, C, K = list(map(int, open(0).read().split()))

    if abs(A - B) > 10**18:
        print('Unfair')
    else:
        if K % 2:
            print((B - A))
        else:
            print((A - B))


main()
# Original solution
A,B,C,K = list(map(int,input().split()))
if A == B == C:
  print((0))
  exit()
for _ in range(K):
  A,B,C = B+C,A+C,A+B
  ans = abs(A-B)
  if ans > 10**18:
    print('Unfair')
    exit()

print((A-B))

# Optimized solution
A,B,C,K = list(map(int,input().split()))
ans = A-B
if abs(ans) > 10**18:
  ans = 'Unfair'
else:
  if K%2 != 0:
    ans = B-A
print(ans)
# Original solution
a,b,c,k=list(map(int,input().split()))
if a==b==c:
    print((0))
    exit()
for i in range(k):
    A=c+b;B=a+c;C=a+b
    a=A;b=B;c=C
if abs(a-b)>10**18:
    print("Unfair")
else:
    print((a-b))

# Optimized solution
a,b,c,k=list(map(int,input().split()))
if a==b==c:
    print((0))
    exit()
elif abs(a-b)>10**18:
    print("Unfair")
elif k%2==1:
    print((b-a))
else:
    print((a-b))
# Original solution
N = [int(i) for i in input().split()]
A = N[0]
B = N[1]
C = N[2]
K = N[3]

if A == B == C:
    print((0))
else:
    for i in range(K):
        NA = B + C
        NB = A + C
        NC = A + B
        A = NA
        B = NB
        C = NC
    if abs(A-B) > 10 ** 18:
        print('Unfair')
    else:
        print((A-B))

# Optimized solution
N = [int(i) for i in input().split()]
A = N[0]
B = N[1]
C = N[2]
K = N[3]

if K % 2 == 0:
    if abs(A - B) > 10 ** 18:
        print('Unfair')
    else:
        print((A - B))
else :
    if abs(A - B) > 10 ** 18:
        print('Unfair')
    else:
        print((B - A))
# Original solution
a,b,c,k = list(map(int,input().split()))
if a == b:
    print((0))
    exit()
for i in range(k):
    a_o = a
    b_o = b
    c_o = c
    a = b_o + c_o
    b = a_o + c_o
    c = a_o + b_o
    if abs(a-b) > 10**18:
        print("Unfair")
        break
print((a-b))


# Optimized solution
a,b,c,k = list(map(int,input().split()))
ans = a - b
if k % 2 == 0:
    print(ans)
else:
    print((-ans))
# Original solution
A, B, C, K = list(map(int, input().split()))

for i in range(K):
  if A == B and B == C:
    break
  next_A = B + C
  next_B = A + C
  next_C = A + B
  A = next_A
  B = next_B
  C = next_C
if abs(A - B) > 10**18:
  print('Unfair')
else:
  print((A - B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))

if abs(A - B) > 10**18:
  print('Unfair')
else:
  print(((A -B)*(-1)**K))
# Original solution
A, B, C, K = list(map(int, input().split()))

if A == B == C:
    print((0))
    exit()

for i in range(K):
    nA = B + C
    nB = A + C
    nC = A + B
    A, B, C = nA, nB, nC
    if abs(A - B) >= int(1e18):
        print("Unfair")
        break
else:
    print((A - B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))

if K % 2 == 0:
    if abs(A - B) >= int(1e18):
        print("Unfair")
    else:
        print((A - B))
else:
    if abs(A - B) >= int(1e18):
        print("Unfair")
    else:
        print((B - A))
# Original solution
A, B, C, K = list(map(int,input().split()))
ans =  0
if A == B == C:
    ans = 0
    K = 0
while K > 0:
    a = A
    b = B
    c = C
    A = b + c
    B = a + c
    C = a + b
    K -= 1
ans = A - B
if abs(ans) > 10 ** 18:
    ans = 10 ** 18
print(ans)

# Optimized solution
A, B, C, K = list(map(int,input().split()))
ans = A - B
if abs(ans) > 10 ** 18:
    print('Unfair')
elif K % 2 == 1:
    ans *= -1
    print(ans)
else:
    print(ans)
# Original solution
a, b, c, k = list(map(int, input().split()))

flag = True
for i in range(10**18):
    if k == 0:
        break
    if a == b and b == c:
        break
    A = a
    B = b
    C = c
    a = B + C
    b = A + C
    c = A + B
    if i == k - 1:
        break
    if a - b > 10**18 or a-b < -10**18:
        flag = False
        break
if flag:
    print((a - b))
else:
    print('Unfair')


# Optimized solution
a, b, c, k = list(map(int, input().split()))
x = a - b
if x > 10**18:
    print('Unfair')
elif k % 2 == 0:
    print(x)
else:
    print((-x))
# Original solution
A, B, C, K = list(map(int, input().split()))
if A == B == C:
    print((0))
else:
    x = 10**18
    for _ in range(K):
        a = B+C
        b = A+C
        c = A+B
        A=a
        B=b
        C=c
        if A - B > x:
            print("Unfair")
            break
    else:
        print((A-B))

# Optimized solution
A, B, C, K = list(map(int, input().split()))
if K % 2 == 0:
    print((A-B))
else:
    print((B-A))
# Original solution
a,b,c,k = list(map(int,input().split()))
if k % 2 == 0:
    print((a-b))
else:
    print((b-a))

# Optimized solution
a,b,c,k = list(map(int,input().split()))
print(((a-b)*(-1)**(k%2)))
# Original solution
a, b, c, k = list(map(int, input().split()))
if a == b == c:
    print((0))
    exit()
for i in range(k):
    tmp1 = a+b
    tmp2 = b+c
    tmp3 = c+a
    a = tmp2
    b = tmp3
    c = tmp1
    if a-b > 10**18:
        print('Unfair')
        exit()
print((a-b))


# Optimized solution
a, b, c, k = list(map(int, input().split()))
if a == b == c:
    print((0))
elif a-b > 10**18:
    print('Unfair')
else:
    if k % 2 == 0:
        print((a-b))
    else:
        print((b-a))
# Original solution
list1 = list(map(int, input().split()))
a = list1[0]
b = list1[1]
c = list1[2]
k = list1[3]

pointH =a
pointM =b
pointL =c

if a ==b and b ==c:
    print((0))
else:
    index =0
    while index<k:
        list2 = [pointM+pointL,pointL+pointH,pointH+pointM]
        pointH = list2[0]
        pointM = list2[1]
        pointL = list2[2]
        index+=1

    if pointH-pointM>10**18:
        print("Unfair")
    else:
        print((pointH-pointM))

# Optimized solution
list1 = list(map(int, input().split()))
a = list1[0]
b = list1[1]
c = list1[2]
k = list1[3]


if k%2 ==0:
    ans = a-b
else:
    ans = b-a

if ans>10**18:
    print("Unfair")
else:
    print(ans)
# Original solution
A, B, C, K = list(map(int, input().split()))

if A==B and B==C:
  ans = 0
else:
  for i in range(K):
    A, B, C = B+C, A+C, A+B
    if abs(A-B)>10**18:
      break
  ans = A-B
  
if abs(ans)>10**18:
  print("Unfair")
else:
  print(ans)

# Optimized solution
A, B, C, K = list(map(int, input().split()))

if K%2==1:
  print((-A+B))
else:
  print((A-B))
# Original solution
A,B,C,K = list(map(int,input().split()))

print((B-A if K%2 else A-B))


# Optimized solution
A,B,C,K = list(map(int,input().split()))
if K%2:
    print((B-A))
else:
    print((A-B))
# Original solution
A,B,C,K = list(map(int,input().split()))
if K%2:
    print((B-A))
else:
    print((A-B))

# Optimized solution
A,B,C,K = list(map(int,input().split()))
print((B-A if K%2 else A-B))
# Original solution
A, B, C, K = list(map(int, input().split()))

def judge(n):
    if abs(n) > 10**18:
        print('Unfair')
    else:
        print(n)

if K == 0:
    judge(A-B)
else:
    if A == B and B == C and C == A :
        print((0))
    else:
        sum = A + B + C
        for i in range(1, K+1):
            sum *= K
            A = sum - A
            B = sum - B
        judge(A-B)

# Optimized solution
A, B, C, K = list(map(int, input().split()))

def judge(n):
    if abs(n) > 10**18:
        print('Unfair')
    else:
        print(n)

if K % 2 == 0:
    judge(A-B)
else:
     judge(B-A)
# Original solution
inputs = list(map(int, input().split()))
K = inputs.pop()

if inputs[0] == inputs[1] == inputs[2]:
    print((0))
else:
    for k in range(K):
        total = sum(inputs)
        inputs = [total-inputs[i] for i in range(3)]

        if abs(inputs[0] - inputs[1]) > 10 ** 18:
            print((-1))
            break
    else:
        print((inputs[0] - inputs[1]))


# Optimized solution
inputs = list(map(int, input().split()))
K = inputs.pop()

ans = inputs[0] - inputs[1]

print((-1 if abs(ans) > 10 ** 18 else ans * ((-1)**K)))
# Original solution
a,b,c,k = list(map(int, input().split()))
ans = 0
if a==b:
    ans = 0
else:
    for i in range(k):
        a1 = b+c
        b1 = c+a
        c1 = a+b
        a = a1
        b = b1
        c = c1
    if abs(a-b)>=10**18:
        ans = 'Unfair'
    else:
        ans = a-b
print(ans)

# Optimized solution
a,b,c,k = list(map(int, input().split()))
print((0 if a==b else a-b if k%2==0 else b-a))
# Original solution
import sys
from functools import lru_cache

A, B, C, K = list(map(int, input().split()))

@lru_cache(maxsize=None)
def operation(A, B, C):
    return(B+C, C+A, A+B)

if (A==B) & (B==C):
    print((0))
    sys.exit()

for _ in range(K):
    A, B, C = operation(A, B, C)
    if A - B > 10**18:
        print("Unfair")
        sys.exit()

print((A - B))

# Optimized solution
A, B, C, K = map(int, input().split())
print(A-B) if K%2==0 else print(B-A)
# Original solution
a,b,c,K=list(map(int,input().split()))
if a==b and b==c:
  print("0")
  exit()
for i in range(K):
  an=a
  bn=b
  cn=c
  a=bn+cn
  b=an+cn
  c=an+bn
S=a-b
if a-b>=10**18:
  print("Unfair")
  exit()
print((a-b))

# Optimized solution
a,b,c,K=list(map(int,input().split()))
print(((a-b)*((-1)**K)))
# Original solution
inf = 10**18
A,B,C,K = list(map(int,input().split(" ")))
if K % 2 == 1:
	if (B-A) > inf:
		print("Unfair")
	else:
		print((B-A))
else:
	if (A-B) > inf:
		print("Unfair")
	else:
		print((A-B))

# Optimized solution
A,B,C,K = list(map(int,input().split(" ")))

if K % 2 == 1:
	print((B-A))
else:
	print((A-B))
# Original solution
a,b,c,k=list(map(int,input().split()))
n1=1
n2=0
if a==b:print((0));exit()
for i in range(k):
    n1,n2=n2*2,n1+n2
    if abs((n1-n2)*(a-b))>10**18:print("Unfair");exit()
print(((n1-n2)*(a-b)))

# Optimized solution
a,b,c,k=list(map(int,input().split()))
t=-1
if k%2==0:t=1
print((t*(a-b)))
# Original solution
n=eval(input())
a=input()
count=0
for r in range(n):
	b=input()
	lb=len(b)
	flag=0
	for s in range(lb):
		for i in range(lb-(s+1)*(len(a)-1)):
			if b[i:i+(s+1)*len(a):s+1]==a:
				count+=1
				flag=1
				break
		if flag==1:break
print(count)
	

# Optimized solution
n=eval(input())
a=input()
la=len(a)
count=0
for r in range(n):
	b=input()
	lb=len(b)
	flag=0
	for skip in range(lb):
		for ini in range(lb-(skip+1)*(la-1)):
			if b[ini:ini+(skip+1)*la:skip+1]==a:
				count+=1
				flag=1
				break
		if flag==1:break
print(count)
# Original solution
n = eval(input())
s = input()
cnt = 0
for i in range(n):
    judge = False
    p = input()
    for k in range(len(p)):
        for j in range(1, len(p)):
            for l in range(len(s)):
                if k+l*j < len(p) and p[k+l*j] == s[l]:
                    if l+1 >= len(s): judge = True
                    continue
                break
    if judge == True: cnt += 1
print(cnt)

# Optimized solution
n = eval(input())
s = input()
cnt = 0
for i in range(n):
    judge = False
    p = input()
    for k in range(len(p)):
        if judge: break
        for j in range(1, len(p)):
            if judge: break
            for l in range(len(s)):
                if k+l*j < len(p) and p[k+l*j] == s[l]:
                    if l+1 >= len(s): judge = True
                    continue
                break
    if judge == True: cnt += 1
print(cnt)
# Original solution
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))


# Optimized solution
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))
# Original solution
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)


# Optimized solution
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)
# Original solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list([x%m for x in d])
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print((n-1-zero-tmp))

    
    


# Optimized solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list([(x-1)%m+1 for x in d])
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print((n-1-tmp))
# Original solution
import sys
input = sys.stdin.readline
k, q = list(map(int, input().split()))
d = list(map(int, input().split()))

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

for n, x, m in query:
    l = [d[i]%m for i in range(k)]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    rem = n % k
    total = sum(l)%m * count + x%m + sum(l[:rem])
    total //= m
    total += sum(l)//m * count
    zero_total += l[:rem].count(0)

    print((n-total-zero_total))


# Optimized solution
import sys
input = sys.stdin.readline
k, q = list(map(int, input().split()))
d = list(map(int, input().split()))

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

def answer_query(n, x, m):
    l = [d[i]%m for i in range(k)]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]
        if l[i] == 0:
            zero_total += 1

    total //= m
    total += s//m * count

    print((n-total-zero_total))
for n, x, m in query:
    answer_query(n, x, m)