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

N =int(input())
ans = 0
for i in range(1,N):
    if (N//i) == N%i:
        ans += i
print(ans)

### FIXED CODE ###

import math
def prime_divisor(n):
    ls = []
    i = 2
    while i <= math.floor(n**0.5):
        if n%i == 0:
            ls.append(i)
            ls.append(n//i)
            i += 1
        else:
            i += 1
    if n > 1:
        ls.append(n)
    return ls
N = int(input())
ls1 = prime_divisor(N)
ls2 = [x-1 for x in list(set(ls1)) if x >= 2]
ls2.sort()
ls2.reverse()
ans = 0
for i in range(len(ls2)):
    if N // ls2[i] == N % ls2[i]:
        ans += ls2[i]
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
operation = [list(map(int, input().split())) for _ in range(q)]

from  collections import Counter

dict_a = Counter(a)

def answer(q, dict_a):
  for i in range(q):
    dict_a[operation[i][1]] += dict_a[operation[i][0]]
    dict_a[operation[i][0]] = 0
    s = 0
    for (k, v) in dict_a.items():
      s += k*v
    print(s)

answer(q, dict_a)

### FIXED CODE ###

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

from  collections import Counter

dict_a = Counter(a)
s = sum(a)

for i in range(q):
  b, c = map(int, input().split())
  s -= b*dict_a[b]
  s += c*dict_a[b]
  dict_a[c] += dict_a[b]
  dict_a[b] = 0
  print(s)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque()

while route:
    while route:
        y, x = route.popleft()
        wroute.append([y, x])
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])
### BUGGY CODE ###

mod = int(1e9+7)
n, m = [int(num) for num in input().split()]

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

sumx = 0
for i in range(n-1):
    sumx += (sum(x[i+1:]) - x[i] * ((n-1) - (i+1) + 1)) % mod
sumy = 0
for k in range(m-1):
    sumy += (sum(y[k+1:]) - y[k] * ((m-1) - (k+1) + 1)) % mod

ans = ((sumx % mod) * (sumy % mod)) % mod

print(ans)

### FIXED CODE ###

# 予めsx, syを全て計算しておく
# このとき漸化式を使えば毎回全ての話を求める必要がない

mod = int(1e9+7)
n, m = [int(num) for num in input().split()]

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


sx = [0] * n
sx[0] = x[0]
for i in range(n-1):
    sx[i+1] = sx[i] + x[i+1]
sxd = 0  
for i in range(n-1):
    sxd += ((sx[n-1] - sx[i]) - x[i] * ((n-1) - (i+1) + 1)) % mod

sy = [0] * m
sy[0] = y[0]
for k in range(m-1):
    sy[k+1] = sy[k] + y[k+1]
syd = 0
for k in range(m-1):
    syd += ((sy[m-1] - sy[k]) - y[k] * ((m-1) - (k+1) + 1)) % mod

ans = ((sxd % mod) * (syd % mod)) % mod

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

X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a + b)

AB.sort(reverse=True)
AB = AB[:min(3001, X * Y * Z + 1)]
ABC = []
for c in C:
  for ab in AB:
    ABC.append(ab + c)
ABC.sort(reverse=True)

print(*ABC[:K], sep='\n')


### FIXED CODE ###

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

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a + b)

AB.sort(reverse=True)
AB = AB[:min(3001, X * Y * Z + 1)]
ABC = []
for c in C:
  for ab in AB:
    ABC.append(ab + c)
ABC.sort(reverse=True)
for i in range(K):
  print(ABC[i])
### BUGGY CODE ###

# coding: utf-8
import sys
from math import factorial

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


def nCr(n,r):
    return (factorial(n) // factorial(r) // factorial(n - r))


def main():
    k = ni()
    s = ns()
    n = len(s)
    mod = 1000000007
    ans = 0
    tmp1 = factorial(n+k)%mod
    tmp2 = 1
    tmp3 = tmp1
    for m in range(n):
        ans += ((nCr(n+k,m)%mod)*pow(25,n+k-m,mod))%mod
    ans = pow(26,n+k,mod) - ans
    ans %= mod
    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
import sys

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


def main():
    k = ni()
    s = ns()
    n = len(s)
    mod = 1000000007
    ans = 0
    inv25 = pow(25, mod-2, mod)
    tmp1 = 1
    tmp2 = pow(25,n+k,mod)
    for m in range(n):
        ans += (tmp1*tmp2)%mod
        ans %= mod
        tmp1 *= (n+k-m)*pow(m+1,mod-2,mod)
        tmp2 *= inv25
        tmp1 %= mod
        tmp2 %= mod
    ans = pow(26,n+k,mod) - ans
    ans %= mod
    print(ans)
    return


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

s=input()
dp=[[0]*13 for _ in range(len(s))]
if s[0]=='?':
  dp[0]=[1]*10+[0]*3
else:
  dp[0][int(s[0])]+=1

MOD=10**9+7
for i in range(1,len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i][((j*10)%13+k)%13]+=dp[i-1][j]
        dp[i][((j*10)%13+k)%13]%=MOD
  else:
    k=int(s[i])
    for j in range(13):
      dp[i][((j*10)%13+k)%13]+=dp[i-1][j]
      dp[i][((j*10)%13+k)%13]%=MOD
print(dp[-1][5])

### FIXED CODE ###

s=input()
dp=[[0]*13 for _ in range(len(s))]
if s[0]=='?':
  dp[0]=[1]*10+[0]*3
else:
  dp[0][int(s[0])]+=1

MOD=10**9+7
for i in range(1,len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i][((j*10)%13+k)%13]+=dp[i-1][j]
        dp[i][((j*10)%13+k)%13]%=MOD
  else:
    k=int(s[i])
    for j in range(13):
      dp[i][((j*10)%13+k)%13]+=dp[i-1][j]
      dp[i][((j*10)%13+k)%13]%=MOD
print(dp[-1][5])
### BUGGY CODE ###

from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        if dp[i+1][j] == 0:
            d.appendleft((i+1,j))
        dp[i+1][j] = tmp
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        if dp[i][j+1] == 0:
            d.appendleft((i,j+1))
        dp[i][j+1] = tmp
        
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        if dp[i+1][j] == 0:
            d.appendleft((i+1,j))
        dp[i+1][j] = tmp
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        if dp[i][j+1] == 0:
            d.appendleft((i,j+1))
        dp[i][j+1] = tmp
        
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
x = 1
y = 10**18

for i in range(N):
    x *= A[i]
if x > y:
    print("-1")
else:
    print(x)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 1
rec = True
for i in range(N):
    ans = ans * l[i]
    if ans > 10**18:
        rec = False
        break

if rec:
    print(ans)
else:
    print('-1')
### BUGGY CODE ###

import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
s = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
s = np.pad(s, 1, mode='constant')

def main():
    l = np.zeros((h+2, w+2), dtype=np.int64)
    r = np.zeros((h+2, w+2), dtype=np.int64)
    u = np.zeros((h+2, w+2), dtype=np.int64)
    d = np.zeros((h+2, w+2), dtype=np.int64)

    for i in range(1, w+1):
        bl = s[:, i] == '#'
        l[~bl, i] = l[~bl, i-1] + 1
        i = w+1-i
        bl = s[:, i] == '#'
        r[~bl, i] = r[~bl, i+1] + 1
    
    for i in range(1, h+1):
        bl = s[i, :] == '#'
        u[i, ~bl] = u[i-1, ~bl] + 1
        i = h+1-i
        bl = s[i, :] == '#'
        d[i, ~bl] = d[i+1, ~bl] + 1
    
    res = l + r + u + d - 3
    return np.amax(res[1:h+1, 1:w+1])

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
grid = np.pad(grid, 1, mode='constant')

def main():
    cnt = np.zeros((h+2, w+2))
    cnt[grid == '.'] = np.inf
    
    l = cnt.copy()
    r = cnt.copy()
    u = cnt.copy()
    d = cnt.copy()

    for i in range(1, w+1):
        l[1:h+1, i] = np.minimum(l[1:h+1, i], l[1:h+1, i-1]+1)
        i = w + 1 - i
        r[1:h+1, i] = np.minimum(r[1:h+1, i], r[1:h+1, i+1]+1)
    
    for i in range(1, h+1):
        u[i, 1:w+1] = np.minimum(u[i, 1:w+1], u[i-1, 1:w+1]+1)
        i = h + 1 - i
        d[i, 1:w+1] = np.minimum(d[i, 1:w+1], d[i+1, 1:w+1]+1)
    
    res = np.maximum(l + r + u + d - 3, 0).astype(np.int64)
    return np.amax(res)

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

class BIT(object):
    def __init__(self, size):
        self.size = size
        self.bit = [0] * (self.size + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

    def __str__(self):
        return str(self.bit)

n, m = map(int,input().split())
lr = [[] for i in range(m + 1)]
for i in range(n):
    l, r = map(int,input().split())
    lr[r - l + 1].append(l)

bit = BIT(m + 1)
t = 0
for d in range(1, m + 1):
    for l in lr[d]:
        #print(l, l + d)
        bit.add(l, 1)
        #print(bit.bit)
        bit.add(l + d, -1)
        #print(bit.bit)

    t += len(lr[d])
    ans = n - t

    cur = 0
    while cur <= m:
        # bitの0 ~ curまでの総和を加算
        ans += bit.sum(cur)
        cur += d

    print(ans)


### FIXED CODE ###

class BIT(object):
    def __init__(self, size):
        self.size = size
        self.bit = [0] * (self.size + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

    def __str__(self):
        return str(self.bit)

n, m = map(int,input().split())
lr = [[] for i in range(m + 1)]
for i in range(n):
    l, r = map(int,input().split())
    lr[r - l + 1].append(l)

bit = BIT(m + 1)
t = 0
for d in range(1, m + 1):
    for l in lr[d]:
        #print(l, l + d)
        bit.add(l, 1)
        #print(bit.bit)
        bit.add(l + d, -1)
        #print(bit.bit)

    t += len(lr[d])
    ans = n - t

    cur = 0
    while cur <= m:
        # bitの0 ~ curまでの総和を加算
        ans += bit.sum(cur)
        cur += d

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

N=int(input())
P=list(map(int,input().split()))
count=0
for i in range(1,N):
    num = 0
    for j in range(i):
        if P[i]<=P[j]:
            num+=1
    if num==i:
        count+=1
print(count+1)


### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
count=0
min=2*10**5
for i in range(N):
    if P[i]<=min:
        min=P[i]
        count+=1
print(count)
### BUGGY CODE ###

l, r = map(int, input().split())
a = set()
for i in range(l, r):
  for j in range(i + 1, r + 1):
    a.add((i * j) % 2019)
a = list(a)
print(min(a))

### FIXED CODE ###

l, r = map(int, input().split())
a = []
if r - l > 2019:
  for i in range(l, l + 2019):
    for j in range(i + 1, min(r + 1, l + 2020)):
      a.append((i * j) % 2019)
else:
  for i in range(l, r):
    for j in range(i + 1, r + 1):
      a.append((i * j) % 2019)
ans = min(a)
print(ans)
### BUGGY CODE ###

import sys
class SegTree:
    def __init__(self, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

input = sys.stdin.readline

n,Q=map(int,input().split())
xs = []
qs = []
for i in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
for _ in range(Q):
    xs.append((int(input()), 2, 0,0))
xs.sort(key=lambda x:x[0])

mx,XN = 10**9,n
st = SegTree(XN, mx, min)
for t,r,x,i in xs:
    if r == 2:
        c = st.query(0,XN)
        print(c if c!= mx else -1)
    else:
        st.update(i, x if r else mx)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
x=1
for i in A:
  x*=i
if x>1000000000000000000:
  print('-1')
else:
  print(x)

### FIXED CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
if 0 in A:
  print('0')
  sys.exit()
x=1
for i in A:
  x*=i
  if x>1000000000000000000:
    print('-1')
    sys.exit()
print(x)
### BUGGY CODE ###

#import math
from functools import reduce

def gcd(a,b):
    if b>a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

def gcds(nums):
    return reduce(gcd, nums)

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

ans = 0
for i in range(len(a)):
    if i == 0:
        l = 0
    else:
        l = gcds(a[:i])
    
    if i == len(a) - 1:
        r = 0
    else:
        r = gcds(a[(i+1):])
    
    aaa = gcd(l, r)
    
    if ans < aaa:
        ans = aaa
print(ans)

### FIXED CODE ###

import sys
from functools import reduce

input = sys.stdin.readline

def gcd(a,b):
    if b>a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

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


ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])
for i in range(n):
    ans = max(ans, gcd(l[i], r[i+1]))
print(ans)
### BUGGY CODE ###

class TrieNode: 
    def __init__(self): 
    	self.children = [None]*26
    	self.isEndOfWord = False

class Trie: 
    def __init__(self): 
	    self.root = self.getNode() 

    def getNode(self):
        return TrieNode()

    def _charToIndex(self,ch): 
        return ord(ch)-ord('a') 

    def insert(self,key): 
	    pCrawl = self.root 
	    length = len(key) 
	    for level in range(length): 
		    index = self._charToIndex(key[level]) 
		    if not pCrawl.children[index]: 
			    pCrawl.children[index] = self.getNode() 
		    pCrawl = pCrawl.children[index] 
	    pCrawl.isEndOfWord = True
    
    def search(self, key):
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
        return pCrawl != None and pCrawl.isEndOfWord

t = Trie()
count = 0
n = int(input())
for i in range(n):
    s = input()
    if not t.search(s):
        count += 1
        t.insert(s)
print(count)

### FIXED CODE ###

n = int(input())
str_list = []
count = 1
for _ in range(n):
    s = input()
    str_list.append(s)
str_list.sort()
for i in range(n-1):
    if str_list[i] != str_list[i+1]:
        count += 1
print(count)
### BUGGY CODE ###

N = int(input())
nums = [input() for i in range(N)]

max_list = []
for i in range(0, N):
    f_nums = nums[:i]
    l_nums = nums[i+1:]
    f_nums.extend(l_nums)
    _max = max(f_nums)
    max_list.append(_max)

for x in max_list:
    print(x)
    




### FIXED CODE ###

N = int(input())
nums = [int(input()) for i in range(N)]

_nums = sorted(nums, reverse=True)
max1 = _nums[0]
max2 = _nums[1]
for i in range(0, N):
    if nums[i] == max1:
        print(max2)
    else:
        print(max1)
### BUGGY CODE ###

#AGC040A
import sys
s = sys.stdin.readline().rstrip()
n = len(s)
L = [0 for i in range(n+1)]
f = False
while (f==False):
    f = True
    for i in range(n):
        if s[i] =='<' and not L[i+1] >L[i]:
            L[i+1] = L[i]+1
            f = False
        elif s[i] == '>' and not L[i] > L[i+1]:
            L[i] = L[i+1] +1
            f = False
#print(*L)
print(sum(L))

### FIXED CODE ###

#AGC040
import sys
s = sys.stdin.readline().rstrip()
n = len(s)
L = [0 for _ in range(n+1)]

for i in range(n):
    if s[i] == '<':
        L[i+1] = L[i] +1

#print(L)

for i in range(n-1,-1,-1):
    if s[i] == '>':
        L[i] = max(L[i], L[i+1]+1)

#print(L)

print(sum(L))
### BUGGY CODE ###

import bisect
n, m = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
len_aaa = len(aaa)
aaa = sorted([-a for a in aaa])

for i in range(m):
    b, c = list(map(int, input().split(' ')))
    ccc = [-c] * b
    index = bisect.bisect_left(aaa, -c)
    aaa = (aaa[:index] + ccc + aaa[index:])[:len_aaa]
print(abs(sum(aaa)))

### FIXED CODE ###

import bisect
n, m = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
aaa = sorted([-a for a in aaa])[::-1]
len_aaa = len(aaa)

cccbbb = []
for i in range(m):
    b, c = list(map(int, input().split(' ')))
    cccbbb.append((-c, b))
cccbbb = sorted(cccbbb)
ccc = []
for c, b in cccbbb:
    ccc += [c] * b
    if len(ccc) > len_aaa:
        break
ans = 0
for i in range(len_aaa):
    c = ccc[i] if i < len(ccc) else 0
    ans += min(aaa[i], c)
print(abs(ans))
### BUGGY CODE ###

# D - FT Robot

import sys
sys.setrecursionlimit(100000000)

s = list(input())
x, y = map(int, input().split())

f = []
F_counter = 0
for i in range(len(s)):
    if s[i] == "F":
        F_counter += 1
    else:
        f.append(F_counter)
        F_counter = 0
f.append(F_counter)
        
def dp_x(X, f_idx):
    if f_idx == 0:
        return X == f[0]
    elif f_idx % 2 == 1:
        return dp_x(X, f_idx-1)
    else:
        return dp_x(X-f[f_idx], f_idx-2) or dp_x(X+f[f_idx], f_idx-2)
    
def dp_y(Y, f_idx):
    if f_idx == 0:
        return Y == 0
    elif f_idx == 1:
        return Y == f[1] or Y == -f[1]
    elif f_idx % 2 == 0:
        return dp_y(Y, f_idx-1)
    else:
        return dp_y(Y-f[f_idx], f_idx-2) or dp_y(Y+f[f_idx], f_idx-2)
    
print("Yes" if dp_x(x, len(f)-1) and dp_y(y, len(f)-1) else "No")

### FIXED CODE ###

# D - FT Robot

import copy

s = input()
x, y = map(int, input().split())

f = [len(x) for x in s.split("T")]
x -= f[0]
fx = f[2::2]
fy = f[1::2]

x_possible_set = set([0])
for dx in fx:
    tmp = set()
    for current_x in x_possible_set:
        tmp.add(current_x + dx)
        tmp.add(current_x - dx)
    x_possible_set = tmp.copy()

y_possible_set = set([0])
for dy in fy:
    tmp = set()
    for current_y in y_possible_set:
        tmp.add(current_y + dy)
        tmp.add(current_y - dy)
    y_possible_set = tmp.copy()

print("Yes" if x in x_possible_set and y in y_possible_set else "No")
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        md0 = md.count(0)
        smd = [0]
        for i in range(K):
            smd.append(smd[-1] + md[i])
        roop = (n - 1) // K
        amari = (n - 1) % K
        an = x + smd[-1] * roop + smd[amari]
        minus = an // m - x // m
        res = n - 1 - minus - md0 * roop - md[:amari].count(0)
        print(res)


main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()