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

s = input()
ls = len(s)
t = input()
lt = len(t)
td = dict()
for x in t:
  if x not in s:
    print(-1)
    exit(0)
for i in range(lt-1):
  if t[i] not in td:
    td[t[i]] = list()
  td[t[i]].append(t[i+1])
md = [dict() for _ in range(ls)]
cd = dict()
for i in range(ls-1,-1,-1):
  cd[s[i]] = i + ls
for i in range(ls-1,-1,-1):
  if s[i] not in td:
    cd[s[i]] = i
    continue
  for x in td[s[i]]:
    md[i][x] = cd[x]
  cd[s[i]] = i
ans = 0
cur = cd[t[0]]
for i in range(lt-1):
  cur = md[cur][t[i+1]]
  ans += (cur//ls)
  cur %= ls
print(1 + ans*ls+cur)

### FIXED CODE ###

def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = cd.copy()
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

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

from heapq import heappushpop, heapify

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapify(a)
gomi=a[0]
for _ in range(m):
    b,c=map(int,input().split())
    if gomi<c:
        for i in range(b):
            heappushpop(a, c)
        gomi=a[0]
print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
CB=[]
for _ in range(m):
    b, c = map(int, input().split())
    CB.append((c, b))
CB.sort(reverse=True)

for c, b in CB:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] >= c:
            break
        heapq.heappushpop(a, c)

print(sum(a))
### BUGGY CODE ###

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

def A(i, j):
    if i == j:
        return 0
    elif j == i + 1:
        return sum(a[i:i+2])
    else:
        S = sum(a[i:j+1])
        return min([A(i, k) + A(k+1, j) for k in range(i, j)]) + S

print(A(0, N-1))

### FIXED CODE ###

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

A = [[0 for __ in range(N)] for _ in range(N)]
S = [[0 for __ in range(N)] for _ in range(N)]

for i in range(N-1):
    for j in range(i, N):
        S[i][j] = sum(a[i:j+1])

for w in range(1, N):
    for i in range(N):
        j = i + w
        if j >= N:
            break
        
        A[i][j] = min([
            A[i][k] + A[k+1][j] for k in range(i, j)
        ]) + S[i][j]

print(A[0][-1])
### BUGGY CODE ###

import heapq

n = int(input())

g = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())

    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))

ans = []
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    
    res = 0
    # x -> k
    dis = [float("inf")] * n
    dis[x-1] = 0
    pq = [(0, x-1)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dis[node]: continue

        for nxt, cost in g[node]:
            if d + cost < dis[nxt]:
                dis[nxt] = d + cost
                heapq.heappush(pq, (dis[nxt], nxt))
    res += dis[k-1]
    # k -> y
    dis = [float("inf")] * n
    dis[k-1] = 0
    pq = [(0, k-1)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dis[node]: continue

        for nxt, cost in g[node]:
            if d + cost < dis[nxt]:
                dis[nxt] = d + cost
                heapq.heappush(pq, (dis[nxt], nxt))
    res += dis[y-1]
    ans.append(res)

print("\n".join(map(str, ans)))

### FIXED CODE ###

import heapq

n = int(input())

g = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())

    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))

q, k = map(int, input().split())

dis = [float("inf")] * n
dis[k-1] = 0
pq = [(0, k-1)]
while pq:
    d, node = heapq.heappop(pq)
    if d > dis[node]: continue

    for nxt, cost in g[node]:
        if d + cost < dis[nxt]:
            dis[nxt] = d + cost
            heapq.heappush(pq, (dis[nxt], nxt))

ans = []
for i in range(q):
    x, y = map(int, input().split())

    ans.append(dis[x-1]+dis[y-1])

print("\n".join(map(str, ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())

ans = 0
D = {}
for i in range(n):
      s = "".join(sorted(input()))
      if s in D.keys():
            ans += D[s]
            D[s] += 1
      else:
            D[s] = 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)
### BUGGY CODE ###


import collections
_=int(input())
l = list(map(int, input().split()))
c = collections.Counter(l)
M={}
for i,v in c.items():
    M[i] =  v*(v-1)/2
M
for k in l:
    M_ = M.copy()
    M_[k] =  M_[k]*(c[k]-2)/c[k]
    print(int(sum(M_.values())))


### FIXED CODE ###

import collections
_ = int(input())
l = list(map(int, input().split()))
c = collections.Counter(l)
M=0
for v in c.values():
    if v>1:
        M +=  v*(v-1)/2

for k in l:
    print(int(M-c[k]+1))
### BUGGY CODE ###

n = int(input())
count = 0
li = []

for i in range(1, n):
  if n - i == i or [i, n - i] in li or [n - i, i] in li:
    continue
    
  else:
    count += 1
    li.append([i, n - i])
    
print(count)
      

### FIXED CODE ###

n = int(input())
count = 0

if n % 2 != 0:
  n += 1
 
for i in range(1, n // 2):
  if n - i == i:
    continue
    
  else:
    count += 1
    
print(count)
### BUGGY CODE ###

import sys

stdin = sys.stdin

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

sys.setrecursionlimit(100000)
def calc(p, x, li, ans):
    ans[p] += x
    l = len(li[p])
    for i in range(l):
        calc(li[p][i], x, li, ans)


n, q = na()
li = [[] for i in range(n)]
ans = [0 for k in range(n)]

for i in range(n-1):
    a, b = na()
    li[a-1].append(b-1)

for j in range(q):
    p, x = na()
    calc(p-1, x, li, ans)
print(*ans)







### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

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

def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        memo[nv] += memo[v]
        dfs(nv, v)

n, q = na()
g = [deque() for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
memo = [0] * n
for i in range(q):
    #seen = [False] * n
    p, x = na()
    p -= 1
    memo[p] += x

dfs(0, -1)
print(*memo)
### BUGGY CODE ###

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
abd = [[x[0], x[1], x[0] - x[1]] for x in ab]
abd.sort(key=lambda x: -x[2])

sol = 0
while abd:
  player = (n - len(abd)) % 2
  if len(abd) % 2:
    eat = min(range(len(abd)), key=lambda x: 2e9*abd[x][2] - abd[x][player])
  else:
    eat = min(range(len(abd)), key=lambda x: abd[x][2] - 2e9*abd[x][player])
  if player:
    sol -= abd[eat][player]
  else:
    sol += abd[eat][player]
  del abd[eat]
print(sol)
  




### FIXED CODE ###

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

ab.sort(key=sum, reverse=True)

sol = 0

for i, x in enumerate(ab):
  if i % 2:
    sol -= ab[i][1]
  else:
    sol += ab[i][0]

print(sol)
### BUGGY CODE ###


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

ans = 0
for ix, word in  enumerate(words):
    word_list = list(word)
    word_list.sort()
    for j, compe_word in enumerate(words[ix+1:]):
        compe_word_list = list(compe_word)
        compe_word_list.sort()
        if ''.join(map(str, compe_word_list)) == ''.join(map(str, word_list)):
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
dic = {}

for i in range(N):
    spell = ''.join(sorted(input()))
    if spell in dic.keys():
        dic[spell] += 1
    else:
        dic[spell] = 1

count = 0
for num in dic.values():
    count += sum([i for i in range(num)])

print(count)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
d = {}
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] != s[j]:
            d[(i, j)] = s[i] + s[j]

for k, v in d.items():
    for i in range(k[1]+1, n):
        if s[k[0]] == s[i]:
            continue
        if s[k[1]] == s[i]:
            continue
        if k[1] - k[0] != i - k[1]:
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
r = 0
g = 0
b = 0

for c in s:
    if c == "R":
        r += 1
    elif c == "G":
        g += 1
    elif c == "B":
        b += 1

sub = 0
for i in range(n):
    for j in range(i+1, n):
        k = j * 2 - i
        if k >= n:
            continue
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            sub += 1

print(r*g*b-sub)
### BUGGY CODE ###

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

def main():
    scores = []
    score = 1
    for i in range(k-1, -1, -1):
        score *= a[i]

    scores.append(score)
    scores_append = scores.append

    for j in range(k, n):
        scores_append(scores[-1] * a[j] / a[j-k])
        if scores[-1] > scores[-2]:
            print('Yes')
        else:
            print('No')

            
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque


def bfs(si, sj):
    q = deque()
    used = set()
    if grids[sj][si] == '#':
        q.append([si, sj, 1])
    else:
        q.append([si, sj, 0])
    used.add(tuple([si, sj]))

    ans = float('inf')
    while len(q) > 0:
        prv_si, prv_sj, num_b = q.popleft()
        if [prv_si, prv_sj] == [W - 1, H - 1]:
            ans = min(ans, num_b)

        else:
            if prv_si < W - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj][prv_si + 1] == '#':
                    q.append([prv_si + 1, prv_sj, num_b + 1])
                else:
                    q.append([prv_si + 1, prv_sj, num_b])
                used.add(tuple([prv_si + 1, prv_sj]))

            if prv_sj < H - 1:
                if grids[prv_sj][prv_si] == '.' and grids[prv_sj + 1][prv_si] == '#':
                    q.append([prv_si, prv_sj + 1, num_b + 1])
                else:
                    q.append([prv_si, prv_sj + 1, num_b])
                used.add(tuple([prv_si, prv_sj + 1]))
    return ans


H, W = map(int, input().split())
grids = [input() for _ in range(H)]
print(bfs(0, 0))


### FIXED CODE ###

H, W = map(int, input().split())
grids = [input() for _ in range(H)]
dp = [[float('inf') for _ in range(W)] for _ in range(H)]
if grids[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(W):
    for j in range(H):
        if i == 0 and j == 0:
            continue

        if i - 1 < 0:
            val1 = float('inf')
        elif grids[j][i - 1] == '.' and grids[j][i] == '#':
            val1 = dp[j][i - 1] + 1
        else:
            val1 = dp[j][i - 1]

        if j - 1 < 0:
            val2 = float('inf')
        elif grids[j - 1][i] == '.' and grids[j][i] == '#':
            val2 = dp[j - 1][i] + 1
        else:
            val2 = dp[j - 1][i]

        dp[j][i] = min(val1, val2)
        #print(i,j,dp)

#print(dp)
print(dp[-1][-1])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
ans = 1
flag = 1
for a in map(int, input().split()):
    ans *= a
    if ans > 10 ** 18:
        flag = 0
    if a == 0:
        flag = 1
        break
if flag == 0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
a_list = np.array(list(map(int, input().split())))
y = np.argsort(a_list)
if a_list[y[0]] == 0:
    print(0)
else:
    ans = 1
    flag = 1
    for i in range(0, n):
        ans *= int(a_list[y[n - 1 - i]])
        if ans > 10 ** 18:
            flag = 0
            break
    if flag == 0:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
dic = {i:0 for i in range(1, N+1)}
c = 0

for i in range(M):
    L, R = map(int, input().split())
    for j in range(L, R+1):
        dic[j] = dic[j] + 1

for id, val in dic.items():
    if val == M:
        c += 1

print(c)

### FIXED CODE ###

N, M = map(int, input().split())
L = 0
R = N

for i in range(M):
    L_new, R_new = map(int, input().split())
    if L < L_new:
        L = L_new
    if R_new < R:
        R = R_new

if L > R:
    print(0)
else:
    print(R-L+1)
### BUGGY CODE ###

import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if 2<len(data):
    if num[0]!=num[1] and num[1]!=num[2]:
        count=int(num[1]/2+1)
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

### FIXED CODE ###

from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)
### BUGGY CODE ###

s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
print(DP[n][5]%(10**9+7))

### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
      DP[i+1][k]%=mod
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)
### BUGGY CODE ###

N, Q=map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

add=[0]*N
for i in range(Q):
  p,x=map(int, input().split())
  add[p-1]+=x

ans=[0]*N
def dfs(start, pre, preval):
  addval=preval+add[start]
  ans[start]+=addval
  for next_node in tree[start]:
    if next_node==pre:
      continue
    dfs(next_node, start,addval)
dfs(0,-1,0)  
for a in ans:
  print(a, end=" ")


### FIXED CODE ###

from collections import deque 
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

print(" ".join(map(str, X)))
### BUGGY CODE ###

#1:初期化
N, K = map(int,input().split())
#h = list(map(int, input().split()))
h = [int(x) for x in input().split()]
#print(h,H)
inf = float("inf")
dp = [inf]*(N) #Kが100までなので余分に入れて安全！

#2:初期値
dp[0] = 0

#3:dp実行部(配るDP)
for i in range(N):
    for k in range(1,min(N-i-1,K)+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
        #print(dp,i,k)

#4:出力
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*- 
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        for k in range(j + 1, n):
            c = L[k]
            if c < a + b:
                ans += 1
            else:
                break
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        k = bisect.bisect_left(L[j + 1:], a + b)
        ans += k
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
total=0
total2=0
count=1
ans=0
for i in range(N):
    total+=A[i]
for i in range(1,N+1):
    total2+=i


if total>total2:
    while True:
        total2 +=N
        count+=1
        if total2>=total:
            if abs(total2-total)<=abs(total2-total-N):
                break
            else:
                count-=1
                break
elif total<total2:
    while True:
        total2 -=N
        count-=1
        if total2<=total:
            if abs(total2-total)<=abs(total2-total-N):
                break
            else:
                count+=1
                break

for i in range(N):
    ans+=abs(A[i]-count)
    count+=1

print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
total=0
for i in range(N):
    B.append(A[i]-i-1)

B.sort()
#print(B)
if len(A)%2==1:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
        #print(B[len(B)//2+1],total)
else:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
print(total)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections


def solve(N: int, S: str):

    dp = collections.defaultdict(set)
    for i,s in enumerate(S):
        for k,v in list(dp.items()):
            for vv in v:
                if vv + len(k) == i:
                    dp[k+s].add(vv)
        dp[s].add(i)
    
    dp_sorted = sorted(((k,v) for k,v in dp.items() if len(v) > 1),key=lambda x:len(x[0]),reverse=True)

    for k,v in dp_sorted:
        if max(v) - min(v) >= len(k):
            print(len(k))
            return

    print(0)

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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

s=str(input())
ans = 0
for i in range(len(s)-3):
  for j in range(i+3,len(s)+1):
    if int(s[i:j]) % 2019 == 0:
      ans += 1
print(ans)

### FIXED CODE ###

s_inv = str(input())[::-1]
dp = [1]+[0]*2018
MOD = 0
ans = 0
num = 0
k = 1

for i in range(len(s_inv)):
  num+=int(s_inv[i])*k
  MOD = num % 2019
  dp[MOD] += 1
  k = k*10
  k %= 2019
for i in dp:
  ans += i*(i-1)/2

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

n = int(input())
m = n
ary = []
for i in range(2,n):
    while True:
        if n % i == 0:
            ary.append(i)
            n /= i
        else:
            break
    if n == 1:
        break
    
if len(ary) == 0:
    print("{}: {}".format(m,m))
else:
    print("{}:".format(m),end="")
    for i in range(len(ary)):
        print(" {}".format(ary[i]),end="")
    print()

### FIXED CODE ###

n = int(input())

def function(n):
    a = []
    if n < 2:
        return a
    while n%2 ==0:
        a.append(2)
        n = n//2
    i = 3
    while i*i <= n:
        if n%i ==0:
            a.append(i)
            n = n//i
        else:
            i += 2
    if n > 1:
        a.append(n)
    return a
print(str(n)+":",*function(n))
### BUGGY CODE ###

from fractions import gcd
P = 10**9+7
N = int(input())
S = list(map(int, input().split()))

temp = S[0]
for i in range(1, N):
    temp = temp*S[i] // gcd(temp, S[i])

ans = 0
for i in range(N):
    ans = (temp//S[i]+ans)%P
print(ans)

### FIXED CODE ###

# from fractions import gcd
# P = 10**9+7
# N = int(input())
# S = list(map(int, input().split()))

# l = {2:0}
# for num in S:
#     temp = num
#     M = temp//2+2
#     cnt = 0
#     while temp%2 == 0:
#         cnt += 1
#         temp //= 2
#     l[2] = max(l[2], cnt)
#     i = 3
#     while temp > 1 and i < M:
#         cnt = 0
#         while temp%i == 0:
#             cnt += 1
#             temp //= i
#         if cnt > 0:
#             if i in l:
#                 l[i] = max(l[i], cnt)
#             else:
#                 l[i] = cnt
#         i += 2
#     if temp > 1:
#         if temp in l:
#             l[temp] = max(l[temp], 1)
#         else:
#             l[temp] = 1
    
    
# ans = 0
# for i in range(N):
#     ans = (temp//S[i]+ans)%P
# print(ans)



from fractions import gcd
P = 10**9+7
N = int(input())
S = list(map(int, input().split()))
 
temp = S[0]
for i in range(1, N):
    temp = temp*S[i] // gcd(temp, S[i])
temp %= P
 
ans = 0
for num in S:
    ans = ((temp*pow(num, P-2, P))%P+ans)%P
print(ans)
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
b = b + a
c = c + b
ans = 0
if k <= a:
    for _ in range(k):
        ans += 1
elif k <= b:
    ans = a
else:
    ans = a
    for _ in range(k-b):
        ans -= 1
print(ans)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = 0
if k <= a:
    ans = k
elif k <= b+a:
    ans = a
else:
    ans = a - (k-(a+b))
print(ans)
### BUGGY CODE ###

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

ans = float('inf')

for i in range(L, R+1) :
    for j in range(i+1,R+1) :
        ans = min(ans, (i*j) % 2019)

print(ans)

### FIXED CODE ###

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

ans = float('inf')

for i in range(L, min(R+1,L+2020)) :
    for j in range(i+1,min(R+1,i+2020)) :
        ans = min(ans, (i*j) % 2019)

print(ans)