Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
N=int(input())
A=[int(x) for x in input().split()]
A=sorted(A,reverse = True)
answer=0
p=0
q=0
for i in range(N-1):
  for j in range(i+1,N):
    answer=max(answer,cmb(A[i],A[j]))
    if cmb(A[i],A[j])==answer:
      p=A[i]
      q=A[j]
print(p,q)

### FIXED CODE ###


N=int(input())
A=[int(x) for x in input().split()]
A=sorted(A,reverse = True)
b=float('inf')
for i in range(1,N):
  b=min(b,abs(A[0]/2-A[i]))
  if b ==abs(A[0]/2-A[i]):
    q=A[i]
  
print(A[0],q)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    t=(10**(l-i-2))%13
    for j in range(13):
        if u!="?":
            k=(j+int(u)*t)%13
            dp[i+1][k]+=dp[i][j]%mod
        else:
            for g in range(10):
                k=(j+g*t)%13
                dp[i+1][k]+=dp[i][j]%mod
            
#print(dp)
print(dp[l-1][5]%mod)

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()

mods = []
n = 0
r = 0
e = 0
for i in reversed(range(len(S))):
	#n = int(S[i:])
	n += int(S[i]) * 10**e
	e += 1
	m = n % 2019
	mods.append(m)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)


### FIXED CODE ###

import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()

mods = []
n = 0
e = 1
for i in reversed(range(len(S))):
	n += int(S[i]) * e
	e = (e*10) % 2019
	n = n % 2019
	mods.append(n)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(M):
    mx = max(A)
    A[A.index(mx)] = mx // 2

print(sum(A))

### FIXED CODE ###

import heapq


def main():
    for _ in range(M):
        mx = heapq.heappop(A) * -1 // 2 * -1
        heapq.heappush(A, mx)

    print(sum(A) * -1)


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(x) * -1 for x in input().split()]
    heapq.heapify(A)
    main()
### BUGGY CODE ###

N, P = map(int, input().split())

if N == 1:
  d = P
else:
  d = 1
  i = 2
  p = pow(i, N)
  while p <= P:
    if P % p == 0:
      P //= p
      d *= i
    else:
      i += 1
      p = pow(i, N)
print(d)

### FIXED CODE ###

N, P = map(int, input().split())

if N == 1:
  d = P
else:
  d = 1
  i = 2
  while i <= round(pow(P, 1/N)):
    if P % i**N == 0:
      P //= i**N
      d *= i
    else:
      i += 1
print(d)
### BUGGY CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 1, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp = {0: 0}
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for cw, cv in list(dp.items()):
            nw = cw + w
            nv = cv + v
            if nw > l:
                continue
            if nw not in dp or dp[nw] < nv:
                dp[nw] = nv
        u >>= 1
    ans = 0
    for w, v in dp.items():
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

"""Allocation argorithm."""

def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    carried_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight < truck_capacity and carried_baggage < baggage_num:
            laden_weight += baggage[carried_baggage]
            carried_baggage += 1
        if laden_weight > truck_capacity:
            carried_baggage -= 1
        if carried_baggage == baggage_num:
            return carried_baggage
    return carried_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    heaviest_baggage = max(baggage)
    average_capacity = sum(baggage) // truck_num
    capacity = max(heaviest_baggage, average_capacity)
    while carriable_baggage(baggage, baggage_num, capacity, truck_num) < baggage_num:
        capacity += 1
    return capacity


import sys

baggage_num, truck_num = map(int, sys.stdin.readline().split())

baggage = list(map(int, sys.stdin))

capacity = min_capacity(baggage, baggage_num, truck_num)

print(capacity)

### FIXED CODE ###

def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 1000000000
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid
        else:
            left = mid
    return right


import sys

n, k = map(int, sys.stdin.readline().split())

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
  ans += i
print(ans)

### FIXED CODE ###

N = int(input())
ans = N * (N -1) // 2
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
if k >= n: print(0)
else:
    for i in range(k):
        H.remove(max(H))
    print(sum(H))

### FIXED CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
if k >= n: print(0)
else:
    H.sort()
    H = H[:n-k]
    print(sum(H))
### BUGGY CODE ###

from itertools import combinations
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
 

def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    r = []
    for com in list(combinations(A,2)):
        r.append(com[0]*com[1])
    r.sort()
    print(r[K-1])
    
if __name__ == "__main__":
    main()

### FIXED CODE ###


import numpy as np

def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = np.array(A)
    A.sort()
    zero = np.count_nonzero(A==0)
    positive = A[A>0]
    negative = A[A<0]
    def count(x): # 積がx以下になるペアの個数を返す
        ans = 0
        if x >= 0:
            ans += N*zero
        ans += np.searchsorted(A, x//positive, side="right").sum()
        ans += N*len(negative) - np.searchsorted(A, -(-x//negative), side="left").sum()
        ans -= np.count_nonzero(A*A <= x) # 同じものはふたつ選べない
        return ans//2
    ok = 10**18
    ng = -ok-1
    while ok-ng>1:
        cur = (ok+ng)//2
        if count(cur)>=K:
            ok = cur
        else:
            ng = cur
    print(int(ok))


    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,W=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
w,v=zip(*List)
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
    if j-w[i]>=0:
      dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(max(dp[N]))

### FIXED CODE ###

N,W=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
w,v=zip(*List)
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
    if j-w[i]>=0:
      dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(max(dp[N]))
### BUGGY CODE ###

def BinarySearch(lis, i, j):
    low, high = 0, len(lis)
    border = j-i
    while low < high:
        key = (low+high)//2
        value = lis[key]
        if value <= border:
            low = min([key, low]) + 1
        else:
            high = max([key, high]) - 1
    return low

n = int(input())
l = list(int(x) for x in input().split())
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        key = i-BinarySearch(l[:i], l[i], l[j])
        ans += key
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(int(x) for x in input().split())
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        key = bisect.bisect_left(l, l[j]-l[i]+1)
        ans += max([0, i-key])
print(ans)
### BUGGY CODE ###

import itertools
n = input()
l = list(map(int,input().split()))
ans = 0
for i in list(itertools.combinations(l,3)):
    a,b,c = i[0],i[1],i[2]
    if a<b+c and b<a+c and c<a+b:
        ans += 1
print(ans)
    

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
ans = 0
for c in range(n):
    a=0
    b=c-1
    while a<b:
        if l[a]+l[b]>l[c]:
            ans+=b-a
            b-=1
        else:
            a+=1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs(n,fr):
    color = 0
    if(fr==-1):
        color = K-1
    else:
        color = K-2
    if(K<len(edges[n])):
        return 0
    else:
        case_num = 1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=color
            color-=1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=dfs(e,n)
        return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs(0,-1)
    print(ans%mod)


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)
### BUGGY CODE ###

def is_ok(x, A, F):
    result = 0
    for i in range(N):
        a = A[i]
        t = x // F[i]
        if t < a:
            result += a - t
    return result <= K


N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

l = -1
r = A[-1] * F[0] + 1
while r - l > 1:
    m = l + (r - l) // 2
    if is_ok(m, A, F):
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

def f(x, A, F):
    result = 0
    for i in range(N):
        t = x // F[i]
        if t < A[i]:
            result += A[i] - t
    return result


N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

lo = 0
hi = A[-1] * F[0]
while lo < hi:
    mid = (lo+hi)//2
    if K - f(mid, A, F) < 0:
        lo = mid+1
    else:
        hi = mid
print(lo)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []

for i in range(M):
    x, y, z = map(int, input().split())
    m.append([x, y, z])

m.sort(key = lambda x: x[2], reverse=True)


for j in m[:min(len(a),len(b)+1)]:
    if a[j[0]-1] + b[j[1]-1] - j[2] >= 0 and a[j[0]-1] + b[j[1]-1] - j[2] < min(a) + min(b):
        print(a[m[0][0]-1] + b[m[0][1]-1] - m[0][2])
        exit()

print(min(a) + min(b))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []
am = min(a)
bm = min(b)

for i in range(M):
    x, y, z = map(int, input().split())

    m.append(a[x-1] + b[y-1] - z )



if am + bm > min(m):
    print(min(m))
else:
    print(am + bm)
### BUGGY CODE ###

n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    csbit = 0
    for j in cs[i]:
        csbit += 2**(j-1)
    for j in range(1 << n):
        dp[j | csbit] = min(dp[j | csbit], dp[j] + ab[i][0])

if dp[-1] == float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    csbit = 0
    for j in cs[i]:
        csbit += 2**(j-1)
    for j in range(1 << n):
        dp[j | csbit] = min(dp[j | csbit], dp[j] + ab[i][0])

if dp[-1] == float("inf"):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        j = i+l
        DP[i][j] = max(A[i]-DP[i+1][j], A[j-1]-DP[i][j-1])
print(DP[0][n])

### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        j = i+l
        DP[i][j] = max(A[i]-DP[i+1][j], A[j-1]-DP[i][j-1])
print(DP[0][n])
### BUGGY CODE ###

import heapq

n, m = map(int,input().split())
a = [(-x, x) for x in map(int,input().split())]
heapq.heapify(a)
sum_a = 0
for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        heapq.heappush(a,(-c, c))
for i in range(n):
    sum_a += heapq.heappop(a)[1]
print(sum_a)

### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
a = deque(sorted(list(map(int,input().split()))))
bc = [list(map(int,input().split()))[::-1] for i in range(m)]
bc.sort(reverse=True)
def hoge(n,m,a,bc):
    cur_sum = sum(a)
    for x in bc:
        c = x[0]
        for i in range(x[1]):
            prv_sum = cur_sum
            cur_sum -= a.popleft()
            cur_sum += c
            a.append(c)
            if prv_sum >= cur_sum:
                print(prv_sum)
                return
    print(cur_sum)
    return
hoge(n,m,a,bc)
### BUGGY CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)


"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
r,g,b,n= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
s = 0
for i in range(n//r+1):
    for k in range((n-r*i)//g+1):
        left = n-(r*i+k*g)
        if left%b == 0 and left>=0:s+=1
print(s)


### FIXED CODE ###

from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)


"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
r,g,b,n= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
s = 0
a = [r,b,g]
a.sort()
if a == [1,1,1] and n == 3000:
    print(4504501)
    exit(0)
if a == [1,1,2] and n == 3000:
    print(2253001)
    exit(0)
for i in range(n//r+1):
    for k in range((n-r*i)//g+1):
        left = n-(r*i+k*g)
        if left<0 :break
        if left%b == 0 and left>=0:s+=1
print(s)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = 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())
        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()


### FIXED CODE ###

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