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

import numpy as np
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)

left = -1
right = 10**18+1
 
 
while right - left > 1:
    mid = left + (right - left) // 2
 
 
    train = k
    for i in range(n):
        req = mid // f[i]
        if req < a[i]:
            train -= a[i] - req
 
 
    if train >= 0:
        right = mid
    else:
        left = mid
 
 
 
print(right)

### FIXED CODE ###

n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)

left = -1
right = 10**18+1
 
 
while right - left > 1:
    mid = left + (right - left) // 2
 
 
    train = k
    for i in range(n):
        req = mid // f[i]
        if req < a[i]:
            train -= a[i] - req
 
 
    if train >= 0:
        right = mid
    else:
        left = mid
 
 
 
print(right)
### BUGGY CODE ###

s = input()
k = int(input())
dic = []

for i in range(len(s)):
    for j in range(i, i + k + 1):
        if dic.count(s[i:j]) == 0:
            dic.append(s[i:j])

print(sorted(dic)[k])

### FIXED CODE ###

s = input()
k = int(input())

dic = [s[i:j] for i in range(len(s)) for j in range(i, i + k + 1)]
print(sorted(set(dic))[k])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W and dp[j+w] < dp[j]+v:
                dp[j+w] = dp[j] + v

    print(max(dp))


main()


### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()
### BUGGY CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = []
    for i in range(n):
        numbers.append(int(raw_input()))
    sigmas = []
    for i in range(1,n+1):
        for j in range(n+1-i):
            sigmas.append(reduce(lambda x,y:x+y,numbers[j:j+i+1]))
    print reduce(lambda x,y:x>y if x else y,sigmas)

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = [int(raw_input()) for i in range(n)]
    if max(numbers) <= 0:
        print max(numbers)
    else:
        ans = 0
        for i in range(n):
            tmp = 0
            for j in range(i,n):
                tmp += numbers[j]
                if(ans<tmp):
                    ans = tmp
        print ans
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
a = [int(sys.stdin.readline()) for _ in range(m)]
mod = 1000000007

def main():
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = dp[0] if not 1 in a else 0
    for i in range(2, n + 1):
        if not i in a:
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod
        else:
            dp[i]=  0
    ans =dp[n]
    return ans
print(main())


### FIXED CODE ###

n, m = map(int, input().split())
mod = 1000000007
a = [True] * (n + 1)
for i in range(m):
    a[int(input())] = False
dp = [0] * (n + 1)
dp[0] = 1

dp[1] = dp[0] if a[1] else 0

for i in range(2, n + 1):
    if a[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod

print(dp[n])
### BUGGY CODE ###

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

cntL = [0] * (M + 1)
for l in L:
    cntL[l] += 1

accCntL = [0] * (M + 2)
for i in range(1, M + 2):
    accCntL[i] = accCntL[i - 1] + cntL[i - 1]

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L):
        if i == j:
            continue
        ans += accCntL[min(A + B, M + 1)] - accCntL[abs(A - B) + 1]

        if abs(A - B) < A < min(A + B, M + 1):
            ans -= 1
        if abs(A - B) < B < min(A + B, M + 1):
            ans -= 1

print(ans // 6)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L[i + 1:], start=i + 1):
        right = bisect_left(L, A + B)
        ans += right - j - 1

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

n = int(input())
a = list(map(int, input().split()))
a.sort()
 
dp = [True] * n
cnt = 0
for i in range(n):
    for j in range(n):
        if i==j:
            continue

        if dp[j]:
            if a[j]%a[i]==0:
                cnt += 1
                dp[j] = False

ans = n - cnt
print(ans)

### FIXED CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
c = Counter(a) # Count num and construct dictionary
c = sorted(c.items(), key=lambda x:x[0]) # align key
ans = 0
isOK = [True] * (10**6+1)

for k, v in c:
    if not isOK[k]:
        continue

    if v > 1:
        for i in range(k, len(isOK), k):
            isOK[i] = False
        continue

    ans += 1
    for i in range(2*k, len(isOK), k):
        isOK[i] = False

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

class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

    def insert(self, key):
        i = len(self.keys)
        self.keys.append(key)
        parent = (i - 1) // 2
        while i > 0 and self.keys[parent] < self.keys[i]:
            self.keys[i], self.keys[parent] = self.keys[parent], self.keys[i]
            i = parent
            parent = (parent - 1) // 2

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        return max_key


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        ans.append(S.heapExtraMax())
    else:
        pass

print(*ans, sep = '\n')

### FIXED CODE ###

def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey
    setHeapDown_max(heap, pos)

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

ans = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        ans.append(heapPop_max(S))
    else:
        pass

print(*ans, sep = '\n')
### BUGGY CODE ###

import sys

input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().strip().split()))
ans = a[0]
for i in range (1,n):
 ans = ans*a[i]
if(ans > 10**18):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import sys

input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().strip().split()))
if(0 in a):
 print(0)
 sys.exit()
else:
 ans = a[0]
 for i in range (1,n):
  ans = ans*a[i]
  if(ans > 10**18):
   print(-1)
   sys.exit()
 print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9+7
table = [0]*(N+1)
table[0] = 1

for i in range(N+1):
    if i+1<=N and (i+1) not in A:
        table[i+1] += table[i]
    if i+2<=N and (i+2) not in A:
        table[i+2] += table[i]

print(table[N]%MOD)

### FIXED CODE ###

N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9+7
table = [0]*(N+1)
table[0] = 1
broken = [1]*(N+1)
for a in A:
    broken[a] = 0

for i in range(N+1):
    if i+1<=N and broken[i+1]:
        table[i+1] += table[i]
    if i+2<=N and broken[i+2]:
        table[i+2] += table[i]

print(table[N]%MOD)
### BUGGY CODE ###

while True:
	try:
		input()
		print(0)
	except EOFError:
		 pass
"""

/*

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


0
1
28
*/

"""

### FIXED CODE ###

from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor//X
	depth=m[''.join(v)][1]
	nextstr=''.join(v)
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'R']
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'L']
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'D']
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'U']
		v[coor],v[coor+X]=v[coor+X],v[coor]

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass
### BUGGY CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    for ans in ANS:
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

N, X, Y = map(int, input().split())

result = []
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if j<=X:
            result.append(j-i)
        else:
            jy = abs(Y-j)
            ix = abs(X-i)
            if (j-i)<=(jy+ix+1):
                result.append(j-i)
            else:
                result.append(jy+ix+1)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

### FIXED CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = [0]*N
for i, j in combinations(range(1, N+1), 2):
    mins = min([j-i, abs(Y-j)+abs(X-i)+1])
    result[mins] += 1
    
for i in range(1, N):
    print(result[i])
### BUGGY CODE ###

def solve():
    s = input()
    q = int(input())
    for i in range(q):
        a = input().split()
        if a[0] == '1':
            s = s[::-1]
        else:
            if a[1] == '2':
                s = s + a[2]
            else:
                s = a[2] + s
    print(s)
solve()


### FIXED CODE ###

def solve():
    s1 = input()
    s2 = ''
    q = int(input())
    flg = 0
    for i in range(q):
        a = input().split()
        if a[0] == '1':
            flg = 1 - flg
        else:
            if flg == 0 and a[1] == '2' or flg == 1 and a[1] == '1':
                s1 += a[2]
            else:
                s2 += a[2]
    if flg == 0:
        print(s2[::-1] + s1)
    else:
        print(s1[::-1] + s2)
solve()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ans = 1
for i in range(n):
    ans *= a[i]
    if ans == 0:
        break
    if ans > 10**18:
        ans = -1
        break

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

X, Y, Z, K = map(int, input().split())

list_cake_1 = []
list_cake_2 = []
list_cake_3 = []

while len(list_cake_1) < X:
	element = list(map(int, input().split()))
	list_cake_1.extend(element)

while len(list_cake_2) < Y:
	element = list(map(int, input().split()))
	list_cake_2.extend(element)
	
while len(list_cake_3) < Z:
	element = list(map(int, input().split()))
	list_cake_3.extend(element)

list_total = []

for i in list_cake_1:
	for j in list_cake_2:
		for k in list_cake_3:
			total_ijk = i+j+k
			list_total.append(total_ijk)
				
list_total.sort()

for i in range(1, K+1):
	print(list_total[-i])

### FIXED CODE ###

import sys

input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())

list_cake_1 = list(map(int, input().split()))
list_cake_2 = list(map(int, input().split()))
list_cake_3 = list(map(int, input().split()))

list_cake_1 = sorted(list_cake_1, reverse=True)
list_cake_2 = sorted(list_cake_2, reverse=True)
list_cake_3 = sorted(list_cake_3, reverse=True)

list_total_sum = []

for i, cake_1 in enumerate(list_cake_1, 1):
	for j, cake_2 in enumerate(list_cake_2, 1):
		for k, cake_3 in enumerate(list_cake_3, 1):
			if i*j*k > K:
				break
			list_total_sum.append(cake_1 + cake_2 + cake_3)

for element in sorted(list_total_sum, reverse=True)[:K]:
	print(element)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = sum(A)
flag = False
for x in range(s, 0, -1):
    if flag:
        break
    sortedA = sorted([a%x for a in A])
    sumA = sum(sortedA)
    index_len = len(sortedA)
    sump = 0
    for i, a in enumerate(sortedA):
        sump += a
        summ = x*(index_len - (i+1)) - (sumA - sump)
        if sump == summ and sump <= K:
            print(x)
            flag = True
            break


### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = sum(A)
flag = False
def make_divisors(n):
    divisors = []
    for i in range(int(n**0.5), 0, -1):
        if n%i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    return sorted(divisors, reverse=True)
divs = make_divisors(s)
for x in divs:
    if flag:
        break
    sortedA = sorted([a%x for a in A])
    sumA = sum(sortedA)
    index_len = len(sortedA)
    sump = 0
    for i, a in enumerate(sortedA):
        sump += a
        summ = x*(index_len - (i+1)) - (sumA - sump)
        if sump == summ and sump <= K:
            print(x)
            flag = True
            break
### BUGGY CODE ###

def main():
    N, D, A = map(int, input().split())
    XH = [list(map(int, input().split())) for _ in range(N)]

    XH.sort()
    result = 0
    for i in range(N):
        x, h = XH[i]
        if h < 0:
            continue
        c = (h + (A - 1)) // A
        result += c
        for j in range(i + 1, N):
            if XH[j][0] > x + 2 * D:
                break
            XH[j][1] -= c * A
    print(result)
main()


### FIXED CODE ###

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
q = []
t = 0
result = 0
for x, h in XH:
    while True:
        if len(q) == 0:
            break
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.pop(0)
    h -= t
    if h < 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)
### BUGGY CODE ###

import copy

input = open(0).read

N, *X = map(int, input().split())


def main():
    a = copy.copy(X)
    a.sort()

    for i in range(N):
        print(a[N // 2] if a.index(X[i]) < N // 2 else a[N // 2 - 1])

    return


main()


### FIXED CODE ###

import copy

input = open(0).read

N, *X = map(int, input().split())


def main():
    a = copy.copy(X)
    l, r = sorted(a)[N // 2 - 1:N // 2 + 1]

    print('\n'.join([str(r) if x < r else str(l) for x in X]))
    return


main()
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[False for j in range(n+1)] for i in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a][b] = True
    way[b][a] = True

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in range(2,n+1):
        if way[room][i] == True:
            q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
alist = list(map(int, input().split()))

for _ in range(m):
  b, c = map(int, input().split())
  alist.extend([c for _ in range(b)])

print(sum(sorted(alist, reverse=True)[:n]))

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
### BUGGY CODE ###

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())
        mods=[d%m for d in D]

        #Sで総和を作成,何回通過したかを計算
        a=sum(mods)
        S=sum(mods)*((n-1)//k)+x%m
        S+=sum(mods[:(n-1)%k])
        through=S//m

        #カウント回数が答え
        ans=n-through-1
        #カウントしたうち0を省く
        ans-=mods.count(0)*((n-1)//k)+mods[:(n-1)%k].count(0)
        print(ans)
main()


### FIXED CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))#結合
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)
### BUGGY CODE ###

L ,R = map(int,input().split())

ans =[]
for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans.append(i*j%2019)
print(min(ans))




### FIXED CODE ###

L ,R = map(int,input().split())

ans =[]
if R - L <= 2019:
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            ans.append(i*j%2019)

else:
    for i in range(R-L-1010,R-L+1010):
        for j in range(i,R-L+1010):
            ans.append(i*j%2019)

print(min(ans))