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

N = int(input())
P = 998244353
A = [int(input()) for _ in range(N)]
s = sum(A)

def calc(m):
    X = [1] + [0] * s
    for a in A:
        for i in range(a, s+1)[::-1]:
            X[i] = (X[i] + X[i-a] * m) % P
    return X

Y = calc(2)
ans = sum([Y[i] for i in range(s//2+1)]) + (0 if s%2 else -calc(1)[s//2])
print((pow(3, N, P) - ans*3) % P)

### FIXED CODE ###

N = int(input())
P = 998244353
A = [int(input()) for _ in range(N)]
s = sum(A)

def calc(m):
    X = [1] + [0] * s
    for a in A:
        for i in range(a, s+1)[::-1]:
            X[i] = (X[i] + X[i-a] * m) % P
    return X

Y = calc(2)
ans = sum([Y[i] for i in range(s//2+1)]) + (0 if s%2 else -calc(1)[s//2])
print((pow(3, N, P) - ans*3) % P)
### BUGGY CODE ###

str = raw_input()
K = int(raw_input())

#print str, K,  len(str)

dic = []

i = 1

while i <= len(str):
    idx = 0
    while True:
        head = idx
        tail = i + idx
        if tail > len(str):
            break
        else:
            dic.append(str[head:tail])
            idx = idx + 1

    i = i + 1


dic_set = list(set(dic))
dic_set.sort()
#print dic_set


print dic_set[K-1]


### FIXED CODE ###

#import time

str = raw_input()
K = int(raw_input())

#t_start = time.time()

#print str, K,  len(str)

#dic = []
dic = set()

i = 1

#while i <= len(str):
while i <= K:
    idx = 0
    while True:
        head = idx
        tail = i + idx
        if tail > len(str):
            break
        else:
#            dic.append(str[head:tail])
            dic.add(str[head:tail])
            idx = idx + 1

    i = i + 1


#dic_set = list(set(dic))
#dic_set.sort()
#print dic_set

dic_set = list(dic)
dic_set.sort()


print dic_set[K-1]
#print time.time() - t_start
### BUGGY CODE ###

import sys
numbers = []
for line in sys.stdin:
	numbers.append(int(line))

max = numbers[2] - numbers[1]


for i in range(1, len(numbers) - 1):
	for j in range(i + 1, len(numbers)):
		if numbers[j] - numbers[i] > max :
			max = numbers[j] - numbers[i]
print(max)


### FIXED CODE ###

import sys
numbers = []
for line in sys.stdin:
	numbers.append(int(line))

answer = numbers[2] - numbers[1]
tmp_min = numbers[1]
for target in range(2, len(numbers)):
	answer =  max(numbers[target] - tmp_min ,answer)
	tmp_min = min(numbers[target] , tmp_min)

print(answer)
### BUGGY CODE ###

n = int(input())
nn = 0
i = 357

while i <= n:
  s = str(i)
  if '3' in s:
    if '5' in s:
      if '7' in s:
        if ('0' in s or '1' in s or '2' in s or '4' in s or '6' in s or '8' in s or '9' in s) is False:
          #print(i)
          nn += 1
  if i % 10 == 7:
    i += 6
  else:
    i +=2
print(nn)

### FIXED CODE ###

def nextn(n):
    if n == 0:
        return 3
    elif n % 10 == 3:
        return n+2
    elif n % 10== 5:
        return n+2
    elif n % 10 ==7:
        return nextn(n//10)*10 + 3

N = int(input())
n = 357
ans = 0
while n <= N:
    s = str(n)
    a = [False,False,False]
    for c in s:
        if c == '3':
            a[0] = True
        elif c == '5':
            a[1] = True
        elif c == '7':
            a[2] = True
        else:
            print(s)
    if all(a):
        ans += 1
    n = nextn(n) 
print(ans)
### BUGGY CODE ###

n = int(input())

a = list(map(int,input().split()))

L = sum(a)

nagasa = 0

ans = 0

i=0
while(i < len(a)):
  nagasa += a[i]
  if nagasa == L/2:
    break
  elif nagasa > L/2:
    sa1 = L/2 - sum(a[0:i])
    sa2 = nagasa - L/2
  
    if sa1 < sa2:
      # 後ろを減らす
      a[i] -= 1
    else:
      # 前を減らす
      a[i-1] -= 1
    
    L = sum(a)
    ans += 1
    i = 0
    nagasa = 0
  else:
    i+=1

print(ans)



    



### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))

L = sum(a)

nagasa = 0

ans = 0

i=0

for i in range(n):
  nagasa += a[i]
  if nagasa*2 >= L:
    ans = min(abs(L - (nagasa *2)), abs(L - ((nagasa-a[i])*2)))

    break
    

print(ans)
### BUGGY CODE ###

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
        
def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data

def insert(node, x):
    if node is None : return Node(x)
    elif x < node.data :
        node.left = insert(node.left, x)
    else :
        node.right = insert(node.right, x)
    return node

def delete_min(node):
    if node.left is None : return node.right
    node.left = delete_min(node.left)
    return node

def delete(node, x):
    if node is not None :
        if x == node.data :
            if node.left is None :
                return node.right
            elif node.right is None:
                return node.left
            else :
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data :
            node.left = delete(node.left, x)
        else :
            node.right = delete(node.right, x)
    return node

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
Tree = None
for i in range(L) : Tree = insert(Tree,A[i])
ANS = [str(search_min(Tree)[0])]

for i in range(L,N):
    Tree = delete(Tree, A[i-L])
    Tree = insert(Tree, A[i])
    ANS.append(str(search_min(Tree)[0]))
    
print(" ".join(ANS))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

A,B,N = map(int,input().split())
res = 0
for i in range(1,N+1):
    res_bar = (A*i)//B-A*(i//B)
    if res_bar >= res:
        res = res_bar
    else:
        break
print(res)


### FIXED CODE ###

import math
 
a, b, n = map(int, input().split())
ans = 0
tmp = 0
 
if n > b - 1:
    n = b-1
 
ans = math.floor(a*n/b) - a*math.floor(n/b)
 
print(ans)
### BUGGY CODE ###

import sys
import math
import copy
from functools import lru_cache
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    local_robots = copy.deepcopy(robots)
    for i, current in enumerate(robots):
        if count_collisions(current, local_robots) > 0:
            local_robots.remove(current)
            total -= 1
        else:
            prev = current
            
    return total

def count_collisions(current, robots):
    count = 0
    for robot in robots:
        if collision(current[0], current[1], robot[0], robot[1]):
            count += 1
    return count

@lru_cache(maxsize=None)
def collision(currentX, currentL, robotX, rootL):
    return robotX < currentX and robotX+ rootL > currentX - currentL or currentX < robotX and currentX + currentL > robotX - rootL

N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = list(reversed(sorted(ROBOTS, key=lambda x: count_collisions(x, ROBOTS))))
print(solve(ROBOTS))

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    for current in robots:
        if prev and prev[0] + prev[1] > current[0] - current[1]:
            total -= 1
        else:
            prev = current
            
    return total
 
N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = sorted(ROBOTS, key=lambda x: x[0] + x[1])
print(solve(ROBOTS))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

ans = []
for i in range(1, n+1):
    ans.append(str(a.index(i)+1))

print(' '.join(ans))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

ans = [0]*n

for i in range(n):
    ans[a[i]-1] = str(i+1)

print(' '.join(ans))
### BUGGY CODE ###

n = int(input())
ans = 0

for i in range(1,n):
    hoge = n - i
    for j in range(1,hoge+1):
        if hoge % j == 0:
            ans += 1

print(ans)

### FIXED CODE ###

import collections

zzz = 1
nn = int(input())
ans = 0

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

for i in range(1,nn):
    zzz = 1
    cc = collections.Counter(prime_factorize(i))
    hoge = cc.values()
    for aaa in hoge:
        zzz *= aaa + 1
    ans += zzz
   
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from collections import deque

input_buffer = """

"""
#8
#1 2
#2 3
#2 4
#2 5
#4 7
#5 6
#6 8

INPUT = list(reversed(input_buffer.strip().splitlines()))
if INPUT:
    n = int(INPUT.pop())
    edges = [0] * (n-1)
    for i in range(n-1):
        edges[i] = tuple(map(int, INPUT.pop().split()))
else:
    n = int(input())
    edges = [0] * (n-1)
    for i in range(n-1):
        edges[i] = tuple(map(int, input().split()))
    

adjacency_list = [[] for i in range(n+1)]
for edge in edges:
    adjacency_list[edge[0]].append(edge[1])
    adjacency_list[edge[1]].append(edge[0])


max_order = max(len(i) for i in adjacency_list)
root = 0
for i in range(0, n+1):
    if len(adjacency_list[i]) == max_order:
        root = i
             

node_history = set()
edge_dict = dict()
node_deque = deque()


node_deque.append(root)
while len(node_deque):
    current_node = node_deque.popleft()
    undef_edges = []
    kinds = {i for i in range(1, max_order + 1)}
    
    for a in adjacency_list[current_node]:
        if a not in node_history:
            node_history.add(a)
            node_deque.append(a)
            
        if current_node < a:
            temp_edge = (current_node, a)
        else:
            temp_edge = (a, current_node)    
        
        if temp_edge in edge_dict.keys():
            kinds.remove(edge_dict[temp_edge])
        else:
            undef_edges.append(temp_edge)
            
    for undef_edge in undef_edges:
        kind = min(kinds)
        edge_dict[undef_edge] = kind
        kinds.remove(kind)


print(max_order)
for e in edges:
    print(edge_dict[e])


### FIXED CODE ###

from collections import deque

def main():
	N, *AB = map(int, open(0).read().split())
	B = AB[1::2]

	E = [[] for _ in range(N + 1)]
	for a, b in zip(*[iter(AB)] * 2):
		E[a].append(b)

	Q = deque([1])
	C = [0] * (N + 1)
	while Q:
		v = Q.popleft()
		c = 0
		for u in E[v]:
			c += 1 + (c + 1 == C[v])
			C[u] = c
			Q.append(u)

	print(max(C))
	for b in B:
		print(C[b])

main()
### BUGGY CODE ###

from math import sqrt

N = int(input())
A = list(map(int, input().split()))
A.sort()
#print(A)
ans = []
res = []
nans = 0
doubling = 0
i = 0
while i < N:
  a = A[i]
  #sqa = sqrt(a)
  #print(i,a)
  if i == 0:
    flag = False
    while i + 1 < N:
      bufa = A[i+1]
      if bufa == a:
        i += 1
        flag = True
      else:
        break
    if flag:
      nans += 1
      doubling += 1
      ans.append(a)
    else:
      nans += 1
      ans.append(a)
      res.append(a)
  elif i < N-1:
    flag = False
    while i + 1 < N:
      bufa = A[i+1]
      if bufa == a:
        i += 1
        flag = True
      else:
        break
    if flag:
      d = 0
      flag2 = True
      while 1:
        if a%ans[d] == 0:
          flag2 = False
          break
        if nans -1 == d:
          break
        d += 1
      if flag2:
        nans += 1
        doubling += 1
        ans.append(a)
    else:
      d = 0
      flag2 = True
      while 1:
        if a%ans[d] == 0:
          flag2 = False
          break
        if nans -1 == d:
          break
        d += 1
      if flag2:
        nans += 1
        ans.append(a)
        res.append(a)
  else:
    d = 0
    flag2 = True
    while 1:
      if a%ans[d] == 0:
        flag2 = False
        break
      if nans -1 == d:
        break
      d += 1
    if flag2:
      nans += 1
      ans.append(a)
      res.append(a)
  i += 1
        
        
print(len(res))

### FIXED CODE ###

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

A.sort()
maxA = A[-1]
dp = [-1 for i in range(maxA+1)]
for a in A:
  if dp[a] != 0:
    if dp[a] == 1:
      dp[a] = 0
      continue
    dp[a] = 1
    for i in range(2*a, maxA+1, a):
      dp[i] = 0
ans = 0
for a in A:
  if dp[a] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

print(min([S[0:i].count('W') + S[i+1:].count('E') for i in range(N)]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

W_num = [0] * N
E_num = [0] * N

for i in range(1, N):
    k = N - (i - 1) - 2
    W_num[i] = W_num[i-1] + 1 if S[i-1] == 'W' else W_num[i-1]
    E_num[k] = E_num[k+1] + 1 if S[k+1] == 'E' else E_num[k+1]

print(min([W_num[i] + E_num[i] for i in range(N)]))
### BUGGY CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0 #白色のマスの総数
for i in range(H):
    for j in range(W):
        if lst[i][j] == '.':
            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[1, 0], [0,1], [-1, 0], [0, -1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

### FIXED CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)
### BUGGY CODE ###

input1 = input().split(' ')
input2 = input().split(' ')
n = int(input1[0])
k = int(input1[1])
h = input2

for _ in range(k):
  if len(h) == 0:
    break
  h.pop(h.index(max(h)))

h = list(map(int, input2))
print(sum(h))

### FIXED CODE ###

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

if N < K:
  print(0)
else:
  H = list(map(int, input().split()))
  H.sort()
  for _ in range(K):
    del H[-1]
  print(sum(H))
### BUGGY CODE ###

Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = []
for i in range(M):
  danger.append(int(input()))
l = [1, 1]
for i in range(1, N):
  if i in danger:
    l[1] = 0
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N in danger:
  l[1] = 0
print(l[1] % Num)

### FIXED CODE ###

Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = -1
if M != 0:
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b + 1):
    if (a <= i) and (i <= (a + k -1)):
        print(i)
    if ((a + k) <= i) and ((b - k + 1) <= i) and (i <= b):
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(b + 1, a + k)):
    print(i)
for i in range(max(a + k, b - k + 1), b + 1):
    print(i)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

n, m, k = map(int, input().split())
f = [[] for i in range(n)]
BL = [[] for i in range(n)]
ans = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    f[a-1].append(b-1)
    f[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    BL[c-1].append(d-1)
    BL[d-1].append(c-1)
D = {}
parent = [-1] * n
visited = [False] * n
for root in range(n):
    if visited[root]:
        continue
    D[root]  = set([root])
    stack = [root]
    while stack:
        x = stack.pop()
        visited[x] = True
        parent[x] = root
        for t in f[x]:
            if visited[t]:
                continue
            D[root].add(t)
            stack.append(t)
for i in range(n):
    grp = D[parent[i]]
    tans = len(grp) - len(f[i]) - 1
    for block in BL[i]:
        if block in grp:
            tans -= 1
    ans[i] = tans
print(*ans)

### FIXED CODE ###

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

    n, m, k = map(int, input().split())
    f = [[] for i in range(n)]
    BL = [[] for i in range(n)]
    ans = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        f[a-1].append(b-1)
        f[b-1].append(a-1)
    for _ in range(k):
        c, d = map(int, input().split())
        BL[c-1].append(d-1)
        BL[d-1].append(c-1)
    D = {}
    parent = [-1] * n
    visited = [False] * n
    for root in range(n):
        if visited[root]:
            continue
        D[root]  = set([root])
        stack = [root]
        while stack:
            x = stack.pop()
            visited[x] = True
            parent[x] = root
            for t in f[x]:
                if visited[t]:
                    continue
                D[root].add(t)
                stack.append(t)
    for i in range(n):
        grp = D[parent[i]]
        tans = len(grp) - len(f[i]) - 1
        for block in BL[i]:
            if block in grp:
                tans -= 1
        ans[i] = tans
    print(*ans)
main()
### BUGGY CODE ###

import fractions
from functools import reduce

b = input()
a = list(map(int,input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

x = lcm_list(a)
ans = 0

for i in a:
    ans += (x//i)
    ans %= 1000000007

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

b = input()
a = list(map(int,input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

x = lcm_list(a)
ans = 0

for i in a:
    ans += (x//i)
ans %= 1000000007

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

from collections import defaultdict
# クラスカル法を使う

V, E = map(int, input().split())
D = 0
tree = []
vertices = defaultdict(set)
for i in range(V):
    tree.append(i)          # 全ての頂点は自分の頂点 index と同じ index の木に属す
    vertices[i].add(i)

edges = []
for i in range(E):
    s, t, d = map(int, input().split())
    edges.append((s, t, d))

edges.sort(key=lambda x: x[2])
while edges:
    if V == 1:
        break
    s, t, d = edges.pop(0)
    if tree[s] != tree[t]:
        new = min(tree[s], tree[t])
        old = max(tree[s], tree[t])
        vertices[new] = vertices[new] | vertices[old]
        for vertex in vertices[new]:
            tree[vertex] = new

        D += d
        V -= 1
print(D)

### FIXED CODE ###

#!/usr/bin/env python3

from collections import defaultdict
# クラスカル法を使う

V, E = map(int, input().split())
D = 0
tree = []
vertices = defaultdict(set)
for i in range(V):
    tree.append(i)          # 全ての頂点は自分の頂点 index と同じ index の木に属す
    vertices[i].add(i)

edges = []
for i in range(E):
    s, t, d = map(int, input().split())
    edges.append((s, t, d))

edges.sort(key=lambda x: x[2])
while edges:
    if V == 1:
        break
    s, t, d = edges.pop(0)
    if tree[s] != tree[t]:
        new = min(tree[s], tree[t])
        old = max(tree[s], tree[t])
        vertices[new] = vertices[new] | vertices[old]
        for vertex in vertices[old]:
            tree[vertex] = new

        D += d
        V -= 1
print(D)
### BUGGY CODE ###

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

### FIXED CODE ###

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()
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))

ans = 1 #i=1は絶対満たす
for i in range(1,n):
    tmp = 1
    for j in range(0,i):
        if p[i] > p[j]:
            tmp = 0
            break
    ans += tmp
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1 #i=1は絶対満たす
now_min = p[0]
for i in range(1,n):
    if p[i] <= now_min:
        ans+=1
        now_min = p[i]
print(ans)