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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
vmap = dict()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
def dfs(prev, n):
    if prev < n:
        if (prev, n) in vmap:
            return 0 
        else:
            vmap[(prev, n)] = 1
    else:
        if (n, prev) in vmap:
            return 0 
        else:
            vmap[(n, prev)] = 1
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            print(n+1, v+1)
    if child_num % 2 == 0:
        return 1
    else:
        print(n+1, prev+1)
        return 0

dfs(-1, (n - 1) // 2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

a, b, x = map(int, input().split(' '))
ans = 0
for i in range(a, b+1):
    if i % x == 0:
        ans += 1
print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split(' '))
print(b//x-(a-1)//x)
### BUGGY CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))
cards = list(map(int, input().split(" ")))

cards.sort()

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    insert_point = bisect.bisect_left(cards, rewrite_number)

    cards = cards[:insert_point] + ([rewrite_number] * stock_count) + cards[insert_point:]
    # for _ in range(stock_count):
    #     cards.insert(insert_point, rewrite_number)
    
    del cards[:stock_count]

print(sum(cards))


### FIXED CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

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

import sys
sys.setrecursionlimit(10**6)

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

l=[list() for i in range(n)]
s=[0]*(n+1)

def dfs(t,p):
  s[t]+=s[p]
  for c in l[t]:
    if c!=p:
      dfs(c,t)

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

for i in range(q):
  p,q=map(int,input().split())
  s[p-1]+=q

dfs(0,n)

for i in range(n):
  print(s[i],' ',end="")
print()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

n,q=map(int,input().split())
t=[[] for _ in range(n)]
c=[0 for _ in range(n)]

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

for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x

def dsf(ci,pi):
  for i in t[ci]:
    if i != pi:
      c[i] += c[ci]
      dsf(i, ci)

dsf(0,-1)

print(*c)
### BUGGY CODE ###

n=int(input())

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

X=list(set(A))

RES=[]

for i in X:
    a=A.count(i-1)
    b=A.count(i)
    c=A.count(i+1)
    RES.append(a+b+c)
    
print(max(RES))


### FIXED CODE ###

import collections
n=int(input())

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

a=collections.Counter(A)

X=sorted(a.items(), key=lambda x:x[0])

K=[]
V=[]

RES=[]
for i in range(len(X)):
    K.append(X[i][0])
    V.append(X[i][1])

if len(X)>=3:
    for j in range(1,len(X)-1):
        res=V[j]
        if K[j]-1==K[j-1]:
            res+=V[j-1]
        if K[j]+1==K[j+1]:
            res+=V[j+1]
        RES.append(res)
elif len(X)==2:
    if K[0]+1==K[1]:
        RES.append(V[0]+V[1])
    else:
        RES.append(max(V))
else:
    RES.append(V[0])        

print(max(RES))
### BUGGY CODE ###

import sys
from collections import deque

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    friends = [set() for _ in range(n)]
    for i in range(m):
        a, b = nm()
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)

    groups = []
    in_group = [False] * n
    for i in range(n):
        if in_group[i]:
            continue
        d = deque(friends[i])
        group = [i]
        in_group[i] = True
        while d:
            c = d.pop()
            group.append(c)
            in_group[c] = True
            for friend in friends[c]:
                if not in_group[friend]:
                    d.append(friend)
        groups.append(list(set(group)))

    ans = 0
    for group in groups:
        ans = max(ans, len(group))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    friends = [set() for _ in range(n)]
    for i in range(m):
        a, b = nm()
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)

    groups = []
    in_group = [False] * n
    for i in range(n):
        if in_group[i]:
            continue
        d = deque(friends[i])
        group = [i]
        in_group[i] = True
        while d:
            c = d.pop()
            if in_group[c]:
                continue
            group.append(c)
            in_group[c] = True
            for friend in friends[c]:
                if not in_group[friend]:
                    d.append(friend)
        groups.append(group)

    ans = 0
    for group in groups:
        ans = max(ans, len(group))
    print(ans)


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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
N = len(S)
M = 13
#c = [0]*(N)
#for i in range(N):
#    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
#c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1
"""
dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        m = l * c%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(M):
            for l in range(10):
                m = l*c%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(s)*c%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
"""
#print(dp)
print(dp[-1][5]%mod)

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import sys
import heapq as h

input=sys.stdin.readline

N,K=map(int,input().split())
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=map(int,input().split())
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
need=[]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if sushi[i] in need:
            extra.append(sushi[i][0])
        else:
            need.append(sushi[i])
    else:
        extra.append(sushi[i][0])


appendix=[kindmax[i] for i in range(0,N) if kindmax[i]!=0 and (not i in kind)]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

print(ans)

### FIXED CODE ###

import sys
import heapq as h

input=sys.stdin.readline

N,K=map(int,input().split())
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=map(int,input().split())
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
flag=[0 for i in range(0,N+1)]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if flag[sushi[i][1]]==1:
            extra.append(sushi[i][0])
        else:
            flag[sushi[i][1]]=1
    else:
        extra.append(sushi[i][0])


set={i for i in range(1,N+1)}
set-=kind
appendix=[kindmax[i] for i in set if kindmax[i]!=0 ]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

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

n=int(input())
data=list(map(int,input().split()))
num=1
for i in data:
    num*=i
if 10**18<num:
    print(-1)
else:
    print(num)

### FIXED CODE ###

import sys
n=int(input())
data=list(map(int,input().split()))
num=1
if any(i==0 for i in data):
    print(0)
    sys.exit()
else:
    for i in data:
        num*=i
        if 10**18<num:
            print(-1)
            sys.exit()
print(num)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
ans_list = []
for j in range(1, n):
    for i in range(j):
        for k in range(j + 1, n):
            if j - i == k - j:
                continue
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans += 1
                ans_list.append([i,j,k])
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
ans_list = []

R_index = []
G_index = []
B_index = []

for i in range(n):
    if s[i] == 'R':
        R_index.append(i)
    elif s[i] == 'G':
        G_index.append(i)
    elif s[i] == 'B':
        B_index.append(i)

ans = len(R_index) * len(G_index) * len(B_index)

for j in range(1, n-1):
    for i in range(min(n-j-1,j)+1):
        # print(j,i)
        # print(min(n-j-1,j))
        #
        # print(s[j-i],s[j],s[j+i])
        if s[j-i] != s[j] and s[j] != s[j+i] and s[j-i] != s[j+i]:
            # print('here')
            ans -= 1

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

k = int(input())

def gcd(a, b, c):
    x = min(a, b, c)
    result = 1
    for i in range(1, x + 1):
        if a % i == 0 and b % i == 0 and c % i == 0:
            result = i
    return result

ans = 0
d = dict()
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            x = [str(i) for i in sorted([a, b, c])]
            key = ''.join(x)
            if key not in d.keys():
                d[key] = gcd(a, b, c)
            ans += d[key]
print(ans)

### FIXED CODE ###

import math

k = int(input())

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        x = math.gcd(a, b)
        for c in range(1, k + 1):
            ans += math.gcd(x, c)
print(ans)
### BUGGY CODE ###

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

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

GCDs = []

for n in range(N):
    B = A + []
    trash = B.pop(n)
    GCD = B[0]
    for b in B:
        GCD = gcd(GCD, b)
    GCDs.append(GCD)

print(max(GCDs))

### FIXED CODE ###

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

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

L = [0]
R = [0]
for n in range(N-1):
    L.append(gcd(L[-1],A[n]))
    R.append(gcd(R[-1],A[N-n-1]))
    
GCDs = []
for n in range(N):
    GCDs.append(gcd(L[n], R[N-n-1]))
    
print(max(GCDs))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=[0for _ in range(k+1)]
for i in range(k+1):
    for j in range(n):
        f[i]+=a[j]^i
f.sort(key=lambda x:-x)
print(f[0])


### FIXED CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
# f=[0for _ in range(k+1)]
# for i in range(k+1):
#     for j in range(n):
#         f[i]+=a[j]^i
# f.sort(key=lambda x:-x)
a.sort(key=lambda x:-x)
powSize=math.ceil(math.log(k+1)/math.log(2))
digitCnt=[0for _ in range(powSize)]
for i in range(n):
    for j in range(powSize):
        if ( a[i]&(1<<j) )>0:
            digitCnt[j]+=1
ansNum=[0]
for i in range(powSize-1,-1,-1):
    if 2*digitCnt[i]<n: # digitCnt[i]<n-digitCnt[i]
        for j in range(len(ansNum)):
            ansNum[j]+=(1<<i)
            if ansNum[j]>k:
                if ( ansNum[j]&(1<<(i+1)) )>0:
                    ansNum.append(ansNum[j]-(1<<(i+1)))
                ansNum[j]-=(1<<i)
    # print(i,ansNum)

# ansNum=[0for _ in range(powSize)]
# for i in range(powSize):
#     ansNum[i]=( k&(((1<<powSize)-1)<<(i+1)) )
#     for j in range(i):
#         if 2*digitCnt[j]<n:
#             ansNum[i]+=(1<<j)

ans=[0for _ in range(len(ansNum))]
for i in range(n):
    for j in range(len(ansNum)):
        if ansNum[j]<=k:
            ans[j]+=(a[i]^ansNum[j])
# print(a[0],powSize)
# print(digitCnt)
# print(ansNum,ans)
ans.sort(key=lambda x:-x)
print(ans[0])
### BUGGY CODE ###

import numpy as np
#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

LCM=1
#LCM%=mod
for i in range(N):
  LCM=lcm(LCM, A[i])
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  ans%=mod

print(int(ans%mod))



### FIXED CODE ###


#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

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

inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

for mm in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  ds[a][b] = c
  ds[b][a] = c

## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])


#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))


import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))


### FIXED CODE ###

#import time
#t = time.time()
inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

for mm in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  ds[a][b] = c
  ds[b][a] = c

## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])

#print(f'wf finished {time.time() - t}')
#t = time.time()

#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))


import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))

#print(f'search finished {time.time() - t}')
#t = time.time()
### BUGGY CODE ###

from itertools import product
n = int(input())

nums = [0]*n
for i in product(range(1, n//6+1),repeat=3):
  t = i[0]**2 + i[1]**2 + i[2]**2 + i[0]*i[1] + i[1]*i[2] + i[0]*i[2]
  if t <= n: nums[t-1] += 1

print(*nums, sep="\n")

### FIXED CODE ###

from itertools import product
n = int(input())

nums = [0]*(n+1)
for i in product(range(1, int(n**0.5)+1),repeat=3):
  t = i[0]**2 + i[1]**2 + i[2]**2 + i[0]*i[1] + i[1]*i[2] + i[0]*i[2]
  if t <= n: nums[t] += 1

for i in range(1,n+1): print(nums[i])
### BUGGY CODE ###

S = input()
N = len(S)

dp = [[-float('inf') for _ in range(N + 1)] for _ in range(N + 1)]  # dp[ターン][パーを出せる回数] = score

dp[0][0] = 0

for turn in range(N) :
    for count in range(N + 1) :
        if count > turn :
            break
        dp[turn + 1][count + 1] = max(
            dp[turn + 1][count + 1],
            dp[turn][count] - (1 if S[turn] == 'p' else 0)
        )
        if count > 0 :
            dp[turn + 1][count - 1] = max(
                dp[turn + 1][count - 1],
                dp[turn][count] + (1 if S[turn] == 'g' else 0)
            )

ans = -float('inf')
for i in range(N + 1) :
    ans = max(ans, dp[N][i])
print(ans)

### FIXED CODE ###

S = input()

count = 0
for s in S :
    if s == 'p' :
        count += 1

ans = -count + len(S) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
ans = []

for _ in range(N):
    s = input()
    if s not in ans:
        ans.append(s)
print(len(ans))

### FIXED CODE ###

N = int(input())
ans = set()

for _ in range(N):
    s = input()
    ans.add(s)
print(len(ans))
### BUGGY CODE ###

from array import array
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [array('L', [0 for j in range(tlen + 1)]) for i in range(slen + 1)]
  for i in range(slen):
    dpi1 = dp[i + 1]
    for j in range(tlen):
      if s[i] == t[j]:
        dpi1[j + 1] = max(dpi1[j + 1], dp[i][j] + 1, dpi1[j], dp[i][j + 1])
      else:
        dpi1[j + 1] = max(dpi1[j + 1], dpi1[j], dp[i][j + 1])
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

import sys

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if a[j] + i == m:
			l.append(b[j])
			count += 1
		else:
			break

	if len(l) != 0:
		maximum = max(l)
		ans += maximum
		l.pop(l.index(maximum))

print(ans)


### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

from fractions import gcd
MOD = 10 ** 9 + 7
def lcm(x, y):
    return (x * y) // gcd(x, y)
input()
A = list(map(int, input().split()))
l = 1
for a in A:
    l = lcm(l, a)
total = 0
for a in A:
    total += l // a % MOD
print(total % MOD)

### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

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

total = 0
for a in A:
    total += l // a

print(total % LARGE)