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

N=int(input())
L=list(map(int,input().split()))
pro=1
for i in range(N):
  pro=pro*L[i]
maxi=1
for i in range(18):
  maxi=maxi*10
if maxi<pro:
  print(-1)
else:
  print(pro)

### FIXED CODE ###

N=int(input())
K=list(map(int,input().split()))
L=sorted(K)
maxi=1
for i in range(18):
  maxi=maxi*10
pro=1
for i in range(N):
  pro=pro*L[i]
  if maxi<pro:
    print(-1)
    break
if maxi>=pro:
  print(pro)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
B,C=1,1
for i in range(K,N):
    for j in range(K):
        B*=A[i-1-j]
        C*=A[i-j]
    if B<C:
        print("Yes")
    else:
        print("No")
    B,C=1,1

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K,N):
    if A[i-K]<A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for x in range(M):
  A.sort(reverse=True)
  A[0]//=2
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(A)
for x in range(M):
  t=(-1)*heapq.heappop(A)
  heapq.heappush(A,(-1)*(t//2))
print(-1*sum(A))
### BUGGY CODE ###

def main():
    n, k = list(map(int, input().split()))
    monsters = list(map(int, input().split()))

    for i in range(k):
        ind = monsters.index(max(monsters))
        monsters[ind] = 0
    print(sum(monsters))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main2():
    n, k = list(map(int, input().split()))
    monsters = list(map(int, input().split()))
    monsters.sort(reverse=True)

    for i in range(k):
        if i >= len(monsters):
            break
        monsters[i] = 0
    print(sum(monsters))

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

K, S = map(int, input().split())
answer = 0
for X in range(K + 1):
    for Y in range(K + 1):
        for Z in range(K + 1):
            if X + Y + Z == S:
                answer += 1

print(answer)

### FIXED CODE ###

K, S = map(int, input().split())
answer = 0

for X in range(K + 1):
    for Y in range(K + 1):
        Z = S - X - Y
        if 0 <= Z and Z <= K:
            answer += 1

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

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

def gcd(a,b):
  return a if b==0 else gcd(b, abs(a%b))

min_gcd = 10**18
for i in range(n):
  for j in range(i+1,n):
    min_gcd = min(min_gcd, gcd(xs[i], xs[j]))
print(min_gcd)

### FIXED CODE ###

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

def gcd(a,b):
  return a if b==0 else gcd(b, abs(a%b))

ret = xs[0]
for x in xs[1:]:
  ret = gcd(ret, x)
print(ret)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N):
    B = A.copy()
    del B[i]
    print(max(B))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A,reverse=True)
for i in range(N):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
K = INT()
sum = 0
 
for n in range(K):
  for m in range(K):
    for l in range(K):
      sum += gcd(n+1, gcd(m+1, l+1))
 
print(sum)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
K = INT()
sum = 0
 
for n in range(K):
  for m in range(K):
    for l in range(K):
      sum += gcd(n+1, gcd(m+1, l+1))
 
print(sum)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(1,n+1):
    ans.append(a.index(i)+1)
print(*ans)

### FIXED CODE ###

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

ans = [0 for i in range(n)]
for i, name in enumerate(a):
    ans[name-1] = i+1
print(*ans)
### BUGGY CODE ###

a,b,c,k = map(int, input().split())

total = 0

while k > 0 and a > 0:
    total += 1
    a -= 1
    k -= 1
    
while k > 0 and b > 0:
    total += 0
    b -= 1
    k -= 1

while k > 0 and c > 0:
    total -= 1
    c -= 1
    k -= 1

print(total)


### FIXED CODE ###

a,b,c,k = map(int, input().split())

total = 0

if k > a:
    k = k-a
    total += a

elif k == a:
    k = 0
    total = a

elif k < a:
    total = k
    k = 0

if k > b:
    k = k-b

elif k == b:
    k = 0

elif k < b:
    k = 0

if k > c:
    total -= c
    k -= c

elif k == c:
    total -= k
    k = 0

elif k < c:
    total -= k
    k = 0
    
print(total)
### BUGGY CODE ###

L,R = map(int,input().split())
list1 = []
i = L
j = L + 1
jcount = 0
while True:
    if i < R:
        list1.append(i*j%2019)
        if j < R:
            j += 1
        else:
            jcount += 1
            j = L+1 + jcount
            i += 1
    else:
        break

if len(list1) == 0:
    print(i*j%2019)

list1.sort()
print(list1[0])

### FIXED CODE ###

import sys
L,R = map(int,input().split())
list1 = []
i = L
j = L + 1
jcount = 0
while True:
    if i < R:
        if i*j %2019 == 0:
            print(0)
            sys.exit()
        list1.append(i*j%2019)
        if j < R:
            j += 1
        else:
            jcount += 1
            j = L+1 + jcount
            i += 1
    else:
        break
if len(list1) == 0:
    print(i*j%2019)
print(min(list1))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
cnt = 0
for i in range(N):
    for u in range(i,N):
        if u-i == A[i]+A[u]:
            cnt += 1
        else:
            pass
print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = []
b = []
ans = 0
for i in range(N):
    a.append(i+1+A[i])
    b.append(i+1-A[i])
b = Counter(b)
for i in a:
    ans += b[i]
print(ans)
### BUGGY CODE ###

s = input()
count = 0
new_s = s.replace("ABC", "BCA", 1)
while s != new_s:
  count += 1
  s = new_s
  new_s = s.replace("ABC", "BCA", 1)

print(count)

### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
def minus(n):
  return 128-n

s = input()
total = 0
new_s = s.replace("BC", "D")
new_s_list = list(new_s)
new_s_list.append("G")
tmp_start = 0
for i in range(len(new_s_list)):
  if new_s_list[i] in {'B', 'C', 'G'}:
    ppp = list(map(minus, map(ord, new_s_list[tmp_start:i])))
    bit = Bit(128)
    ans = 0
    for j, p in enumerate(ppp):
      bit.add(p, 1)
      ans += j + 1 - bit.sum(p)
    total += ans
    tmp_start = i+1

print(total)
### BUGGY CODE ###

import sys

use_clipboard=True
bbn=1000000007
	
#+++++

		
def main():
	h, n = map(int, input().split())
	ii=[]
	for i in range(n):
		a,b=map(int, input().split())
		ii.append([a/b, a, b])
	ii.sort()
	
	_,ma,mb = ii[0]
	tn = (h + ma-1)//ma
	tc = tn * mb
	
	vv=[bbn]*(h+1)
	vv[0]=0
	for i in range(h+1):
		for c,a,b in ii:
			nn = min(i + a, h)
			vv[nn]= min(vv[i] + b, vv[nn])
	
	print(vv[-1])
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
class input_clipboard:
	def __init__(self,s):
		self.input_l=s.splitlines()
		self.ii=0
		
	def input(self):
		ret = self.input_l[self.ii]
		self.ii+=1
		return ret

if __name__ == "__main__":
	if sys.platform =='ios':
		if use_clipboard:
			import clipboard
			input_text=clipboard.get()
			ic=input_clipboard(input_text)
			input = lambda : ic.input()
		else:
			sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

use_clipboard=True
bbn=1000000007
	
#+++++

		
def main():
	h, n = map(int, input().split())
	ii=[]
	for i in range(n):
		a,b=map(int, input().split())
		ii.append([a/b, a, b])
	#ii.sort()
	
	_,ma,mb = ii[0]
	tn = (h + ma-1)//ma
	tc = tn * mb
	
	vv=[bbn]*(h+1)
	vv[0]=0
	for i in range(h+1):
		for c,a,b in ii:
			nn = min(i + a, h)
			vv[nn]= min(vv[i] + b, vv[nn])
	
	print(vv[-1])
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
class input_clipboard:
	def __init__(self,s):
		self.input_l=s.splitlines()
		self.ii=0
		
	def input(self):
		ret = self.input_l[self.ii]
		self.ii+=1
		return ret

if __name__ == "__main__":
	if sys.platform =='ios':
		if use_clipboard:
			import clipboard
			input_text=clipboard.get()
			ic=input_clipboard(input_text)
			input = lambda : ic.input()
		else:
			sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

N,X,Y=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

memo={}
def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if (n,last,turn) in memo:
        return memo[(n,turn)]
    if n==1:
        ret=abs(last-A[N-n])
    elif turn==0:
        ret=max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        ret=min( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動
    memo[(n,turn)]=ret
    return ret


print func(N,Y,0)

### FIXED CODE ###

N,Z,W=map(int,raw_input().split())
a=[]
a=map(int,raw_input().split())

if len(a)!=1:
	print max ( abs(a[-1]-W), abs(a[-2]-a[-1]) )
else:
	print abs(a[0]-W)
### BUGGY CODE ###

N = int(input())
for n in range(1, N + 1):
    ans = 0
    for x in range(1, int(pow(n, 0.5))):
        for y in range(1, int(pow(n, 0.5))):
            for z in range(1, int(pow(n, 0.5))):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n:
                    ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())
A = [0] * 10001
for x in range(1, int(pow(N, 0.5))):
    for y in range(1, int(pow(N, 0.5))):
        for z in range(1, int(pow(N, 0.5))):
            value = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if value > 10000:
                break
            A[value] += 1
for a in A[1:N+1]:
    print(a)
### BUGGY CODE ###

s = input()[::-1]

dp = [1] + [0] * 12
new_dp = [0] * 13

res = [[x * 10 ** i % 13 for x in range(10)] for i in range(6)]
mod = 10 ** 9 + 7

for idx, char in enumerate(s):
    new_dp = [0] * 13
    if char != "?":
        for i in range(13):
            new_i = (i + res[idx % 6][int(char)]) % 13
            new_dp[new_i] += dp[i]
        dp = new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i = (i + res[idx % 6][j]) % 13
                new_dp[new_i] += dp[i]
        dp = [x % mod for x in new_dp]

print(dp[5])


### FIXED CODE ###

S = input()
M = 10**9+7

case = [1] + [0] * 12
temp = [0] * 13
unit = 1
before = 0
for i in reversed(range(len(S))):
    if(S[i] == '?'):
        for k in range(13):
            for j in range(10):
                before = (k - unit * j) % 13
                temp[k] += case[before]
            temp[k] %= M
    else:
        for k in range(13):
            before = (k - unit * int(S[i])) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13
    temp = [0] * 13

print(case[5])
### BUGGY CODE ###

import numpy as np

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

LIMIT = 10**18

# result = np.prod(As)
#
# if result > LIMIT:
#     print(-1)
# else:
#     print(result)

result = 1
for a in As:
    result *= a
    # if result > LIMIT:
    #     result = -1
    #     break

if result > LIMIT:
    print(-1)
else:
    print(result)


### FIXED CODE ###

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

LIMIT = 10**18

if 0 in set(As):
    print(0)
else:
    result = 1
    for a in As:
        result *= a
        if result > LIMIT:
            result = -1
            break
    
    print(result)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)

for i in range(m):
    b , c = map(int,input().split())
    for j in range(b):
        p = heapq.heappop(a)
        if p >= c:
            heapq.heappush(a,p)
            break
        else:
            heapq.heappush(a,c)

print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(lambda x: [int(x),1], input().split()))

for i in range(m):
    b , c = map(int,input().split())
    a.append([c,b])
a.sort(reverse = True)

ans = 0
for x,y in a:
    if y < n:
        ans += x*y
        n = n-y
    elif y >=n:
        ans += x*n
        break
print(ans)
### BUGGY CODE ###

from collections import deque
E = lambda x: (x+1)*(x/2)/x
N, K = map(int, input().split())
sums = deque([0]*K)
ans = 0
for pi in map(int, input().split()):
  sums.popleft(); sums.append(E(pi))
  ans = max(ans, sum(sums))
print(ans)


### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
ans = [0] + list(accumulate(map(lambda x: (int(x)+1)/2., input().split())))
print(max([y-x for x,y in zip(ans, ans[K:])]))
### BUGGY CODE ###

from collections import deque


S = deque(input())
Q = int(input())
QUERY = [input().split(" ") for i in range(Q)]

for query in QUERY:
    #print(query)
    if query[0] == "1":#反転
        S.reverse()
    else:#=="2"
        if query[1] == "1":
            S.appendleft(query[2])
        else:#=="2"
            S.append(query[2])
print("".join(list(S)))

### FIXED CODE ###

from collections import deque


S = deque(input())
Q = int(input())
QUERY = [input().split(" ") for i in range(Q)]
reverse_f = 0

for query in QUERY:
    if query[0] == "1":#反転
        reverse_f = (reverse_f+1)%2
    else:#=="2"
        if query[1] == "1":
            if reverse_f:
                S.append(query[2])
            else:
                S.appendleft(query[2])

        else:#=="2"
            if reverse_f:
                S.appendleft(query[2])
            else:
                S.append(query[2])

if reverse_f:
    S.reverse()
print("".join(list(S)))
### BUGGY CODE ###

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

MOD = 998244353

dp = [0] * (S + 1)
dp[0] = 1

for i in range(N):
    ai = A[i]
    for j in range(S, -1, -1):
        dp[j] = 2 * dp[j]
        if j - ai >= 0:
            dp[j] += dp[j - ai]
        dp[j] %= MOD

print(dp[S])


### FIXED CODE ###

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

MOD = 998244353

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    ai = A[i]
    for j in range(S + 1):
        here = dp[i][j]
        # aiがTに含まれない
        dp[i + 1][j] += here
        # aiがTに含まれるが, Uに含まれない
        dp[i + 1][j] += here

        dp[i + 1][j] %= MOD

        # aiがUに含まれる
        if j + ai <= S:
            dp[i + 1][j + ai] += dp[i][j]
            dp[i + 1][j + ai] %= MOD

print(dp[N][S])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in A:
  ans*=i

print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
  print(0)
  exit()
for i in A:
    if ans > 10**18:
        ans = -1
        break
    ans*=i

print(ans if ans <= 10**18 else -1)
### BUGGY CODE ###

n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	count = 0
	for i in range(1, int(a**0.5)+1):
		if (a % i) == 0:
			count += 1
	if count == 1:
		s += 1
print s

		

### FIXED CODE ###

n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	if a == 1:
		pass
	elif a == 2:
		s += 1
	elif (a%2 == 1):
		for i in xrange(3, (int(a**0.5)+1), 2):
			if a%i==0:
				break	
		else:
			s += 1		
print s
### BUGGY CODE ###

s = list(map(str, input()))
t = list(map(str, input()))

sarr = []
tarr = []
flg = 0
for i in list(range(len(s))):
    if s[i] != t[i]:
        sarr.append(s[i])
        tarr.append(t[i])
        
for i in list(range(len(sarr))):
    if sarr.count(sarr[i]) != tarr.count(tarr[i]):
        flg = 1
    
if len(set(sarr)) == len(set(tarr)) and flg == 0:
    print('Yes')
else:
    print('No')
        



### FIXED CODE ###

s = input()
t = input()

counta={}
countb={}

for i in s:
    if i in counta:
        counta[i] += 1
    else:
        counta[i] = 1

for y in t:
    if y in countb:
        countb[y] += 1
    else:
        countb[y] = 1

if sorted(counta.values())  == sorted(countb.values()):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())

S = []

import collections

for i in range (0, N):
	S.append(str(input()))

S = sorted(S)
cnt = collections.Counter()

for word in S:
	cnt[word] += 1
    
V = cnt.most_common(1)

D = V[0][1]

String = [V[0][0]]

for i in range (1, len(set(S))):
	if cnt.most_common()[i][1] == D:
		String.append(cnt.most_common()[i][0])

for i in range (0, len(String)):
	print(String[i])

### FIXED CODE ###

N = int(input())

S = []

import collections

for i in range (0, N):
	S.append(str(input()))

S = sorted(S)
cnt = collections.Counter()

for word in S:
	cnt[word] += 1
    
mostCommon = cnt.most_common()

D = mostCommon[0][1]
print(mostCommon[0][0])
for i in range(1, len(set(S))):
	if mostCommon[i][1] == D:
		print(mostCommon[i][0])
	else:
		exit()
### BUGGY CODE ###

import itertools

n = int(input())
s = input()
c = list(itertools.combinations(s,3))
l = len(set(c))
print(l)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for j in range(n):
        if s[j] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

ans = 0


def solve():

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

    def dfs(len, a, b):
        global ans

        if len == 1:
            for i in range(a, N):
                if S[a] != S[i]:
                    dfs(2, a, i)
        elif len == 2:
            for i in range(b, N):
                if S[b] != S[i] and S[a] != S[i]:
                    if i - b != b - a:
                        ans += 1

    for i in range(0, N):
        dfs(1, i, 0)

    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###



def solve():

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

    r = S.count('R')
    g = S.count('G')
    b = S.count('B')

    ans = r*g*b

    for i in range(N-2):
        for j in range(i+1, N-1):
            # j - i = k - j
            k = j-i+j
            if k >= N:
                continue
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1

    print(ans)


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

a,b,n = map(int,input().split())
ans = 0
tmp = 0


for i in range(n+1):
    tmp = ((a*i)//b)-a*(i//b)
    if tmp > ans:
        ans = tmp
        tmp = 0

print(ans)

### FIXED CODE ###

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

if b > n:
    print((a*n)//b)
elif b <= n:
    print((a*(b-1))//b)
### BUGGY CODE ###

# E - Flatten

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

modulus = 10 ** 9 + 7

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

def lcm(a, b):
    g = gcd(a, b)
    return g * (a // g) * (b // g)

l = 1
for x in a:
    l = lcm(l, x)

s = sum(l // x for x in a)
print(s % modulus)


### FIXED CODE ###

# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

fact = [factorize(x) for x in a]

fset = set()
for f in fact:
    fset.update(f.keys())

l = {k: 0 for k in fset}
for f in fact:
    for k in f:
        l[k] = max(l[k], f[k])
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)
### BUGGY CODE ###

l = {".":1,"*":-10000}
def x(a):
	m=0
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			d=e-c+1
			for r in N:
				p[r]+=l[a[r][e]]
			m=max(P(p,d),m)
	return int(m**0.5)
	
def P(a,d):
	m=0
	for i in range(n-d+1):
		k = 0
		for j in range(d):
			k+=a[i+j]
			if k<0:break
		else:
			m=max(m,k)
	return m
    
while True:
	n=input()
	if n==0:break
	N=range(n)
	print x([raw_input() for i in N])

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    field = [raw_input() for i in range(n)]
    large = [[0]*(n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if field[i][j] == '.':
                large[i][j] = min(large[i][j - 1], large[i - 1][j], large[i - 1][j - 1]) + 1
    print max(map(max, large))
### BUGGY CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
revflag = 0

for i in query:
    if i[0] == '1':
        revflag = 1 - revflag
    else:
        if (revflag == 0 and i[1] == '1') or (revflag == 1 and i[1] == '2'):
            S = i[2] + S
        else:
            S = S + i[2]

if revflag == 0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
revflag = 0
before = ""
after = ""

for i in query:
    if i[0] == '1':
        revflag = 1 - revflag
    else:
        if (revflag == 0 and i[1] == '1') or (revflag == 1 and i[1] == '2'):
            before += i[2]
        else:
            after += i[2]

if revflag == 0:
    print(before[::-1]+S+after)
else:
    print(after[::-1]+S[::-1]+before)
### BUGGY CODE ###

ans = -float('inf')
n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        ans = max(a[j]-a[i], ans)
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
minr = a[0]
ans = -float('inf')
for i in range(1, n):
    ans = max(a[i]-minr, ans)
    minr = min(a[i], minr)
print(ans)