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


import fractions

"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f


def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = A[0]
    for i in range(1, n):
        l = lcm(l, A[i])
    res = 0
    
    for a in A:
        res += l//a
        res %= mod
    print(res%mod)

main()

### FIXED CODE ###

import functools
"""最大公約数"""
def gcd(a,b):
    import fractions
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f

def m(nums):
    return functools.reduce(lcm, nums)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = m(A)
    res = 0
    print(sum(l// i for i in A) % mod)

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

from collections import deque

n, x, y = map(int, input().split())
graph = dict()
for i in range(1, n+1):
    if i not in graph.keys():
        graph[i] = set()
    if i < n:
        graph[i].add(i+1)
    if i > 1:
        graph[i].add(i-1)
graph[x].add(y)
graph[y].add(x)
dist = [[]]
def bfs(source):
    q = deque()
    q.append(source)
    d = [pow(10, 4)] * (n+1)
    d[source] = 0
    vis = [0] * (n+1)
    while len(q):
        temp = q.popleft()
        for i in graph[temp]:
            if not vis[i]:
                q.append(i)
                vis[i] = 1
            d[i] = min(d[temp]+1, d[i])
    dist.append(d)
for i in range(1, n+1):
    bfs(i)
dp = dict()
for i in range(1, n):
    for j in range(i+1, n+1):
        if dist[i][j] not in dp.keys():
            dp[dist[i][j]] = 0
        dp[dist[i][j]] += 1
for i in range(1, n):
    if i not in dp.keys():
        print(0)
    else:
        print(dp[i])


### FIXED CODE ###

"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
from functools import lru_cache
from collections import defaultdict as dd
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def outln(var): sys.stdout.write(str(var)+"\n")
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, x, y = sp()
dp = dd(int)
for i in range(1, n):
    for j in range(i+1, n+1):
        answer = min(abs(j-i), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
        dp[answer] += 1
for i in range(1, n):
    outln(dp[i])
### BUGGY CODE ###

n, k = map(int,input().split())
while(True):
  nk_abs = abs(n - k)

  if n <= k and n <= nk_abs:
    break
  if k == 1:
    n = 0
    break
  n = nk_abs

print(n)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n % k, k - n % k))
### BUGGY CODE ###

N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
E = [(p + 1)/2 for p in P]
ans = 0
for i in range(N-K+1):
    ans = max(ans, sum(E[i: K+i]))
print(ans)



### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
E = [(p + 1)/2 for p in P]
sumE = sum(E[0:K])
ans = sumE
for i in range(1, N-K+1):
    sumE = sumE - E[i-1] + E[i+K-1]
    ans = max(ans, sumE)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while True:
                prev = N
                N = abs(N-K)
                if prev == N:
                        break
        print(N)

### FIXED CODE ###

import math
N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N >= math.ceil(K / 2):
                N = abs(N-K*(N//K+1))
        print(N)
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(A, B+1):
    if A <= i <= A + K - 1 or B - K + 1 <= i <= B:
        print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())

for i in range(A, min(B, A + K - 1) + 1):
    print(i)
for i in range(max(B - K + 1, A + K), B + 1):
    print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

H_sorted = sorted(H, reverse=True)

for _ in range(K):
    if (not len(H_sorted)):
        break
    H_sorted.pop(0)

print(sum(H_sorted))


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

H_sorted = sorted(H, reverse=True)

print(sum(H_sorted[K:]))
### BUGGY CODE ###

def solver():
    N,W = map(int,input().split())
    item = []
    V_MAX = 0
    for _ in range(N):
        w, v = map(int,input().split())
        V_MAX += v
        item.append([w,v])
    dp = [float('inf')]*(V_MAX+1)
    dp[0] = 0
    pos = [0]
    for w,v in item:
        pos_temp = pos.copy()
        for p in pos:
            pos_temp.append(p)
            if (dp[p]+w <= W):
                dp[p+v] = min(dp[p+v], dp[p]+w)
                pos_temp.append(p+v)
        pos = pos_temp
    print(max(pos))

solver()

### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
item = []
V_MAX = 0
for _ in range(N):
    w, v = map(int,input().split())
    V_MAX += v
    item.append([w,v])
dp = np.array([float('inf')]*(V_MAX+1))
dp[0] = 0
pos = np.array([0]*(V_MAX+1))
pos[0] = 1
for w,v in item:
    dp = np.minimum(dp, np.concatenate([np.array([np.inf]*v),np.roll(dp,v)[v:]]) + np.dot(np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]),w))
    pos = (pos + np.concatenate([np.zeros(v),np.roll(pos,v)[v:]]))
    pos[pos > 0] = 1
res = 0
for i in range(V_MAX + 1):
    if dp[i]<=W and res < i : res = i
print(res)
### BUGGY CODE ###

N = int(input())
table = [list(input()) for _ in range(N)]

cnt = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        if sorted(table[i]) == sorted(table[j]):
            cnt += 1

print(cnt)


### FIXED CODE ###

import collections


def main():
    N = int(input())
    table = [''.join(sorted(list(input()))) for _ in range(N)]
    sort_table = set(table)
    cnt_table = collections.Counter(table)
    ans = 0
    for i in sort_table:
        num_of_i = cnt_table[i]
        if num_of_i <= 1:
            continue
        x = (num_of_i * (num_of_i - 1)) // 2
        ans += x

    print(ans)


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

N, K = map(int, input().split())
tmp = 0

for i in range(N):
    n = i
    count = 0
    while n <= K:
        n *= 2
        count += 1
    tmp += (1/N) * (1/2)**count
print(tmp)



### FIXED CODE ###

N, K = map(int, input().split())
tmp = 0

for i in range(1,N+1):
    n = i
    if n < K:
      count = 0
      while n < K:
        n *= 2
        count += 1
    else:
      count = 0
    tmp += (1/N) * (1/2)**count
#    print(i, count, n, tmp)
print(tmp)
### BUGGY CODE ###

S = input()[::-1]

while len(S) > 0:
    if S[:5] == 'maerd':
        S = S[:5]
    elif S[:5] == 'esare':
        S = S[5:]
    elif S[:6] == 'resare':
        S = S[6:]
    elif S[:7] == 'remaerd':
        S = S[7:]
    else:
        print('NO')
        break

if len(S) == 0:
    print('YES')

### FIXED CODE ###

s = input()
if s.replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","") == "":
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

s = list(input())
q = int(input())
query = [input().split() for _ in range(q)]

reverse = False
for i in query:
    if i[0] == '1':
        if reverse:
            reverse = False
        else:
            reverse = True
        continue
    else:
        if reverse:
            if i[1] == '1':
                s.append(i[2])
            else:
                s.insert(0,i[2])
        else:
            if i[1] == '1':
                s.insert(0,i[2])
            else:
                s.append(i[2])

if reverse:
    s = reversed(s)
    s = ''.join(s)
    print(s)
else:
    print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
query = [input().split() for _ in range(q)]

reverse = False
for i in query:
    if len(i) == 1:
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        if reverse:
            if i[1] == '1':
                s.append(i[2])
            else:
                s.appendleft(i[2])
        else:
            if i[1] == '1':
                s.appendleft(i[2])
            else:
                s.append(i[2])
if reverse:
    s = reversed(s)
    s = ''.join(s)
    print(s)
else:
    s = ''.join(s)
    print(s)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
x=1
P=10**18
for a in A:
  x*=a
if x>P:x=-1
print(x)

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
x=1
P=10**18
if 0 in A:x=0 
else:
  for a in A:
    x*=a
    if x>P:
      x=-1
      break
print(x)
### BUGGY CODE ###

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

check = True
for i in range(0,N-1):
  if H[i] > H[i+1]:
    if H[i] - min(H[i+1:]) >= 2:
      check = False

if check:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
H.reverse()

check = True

for i in range(N-1):
  if H[i] >= H[i+1]:
    continue
  else:
    if H[i+1] - H[i] > 1:
      check = False
      break
    else:
      H[i+1] -= 1
      
if check:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

n = input()
b = []
b_old = []
for i in range(int(n)):
    tmp = input()
    b.append(int(tmp))

count = 1
s = b[0]
if s == 2:
    print(count)
else:
    b_old.append(s)
    n_b = s
    flag = 0
    for i in range(int(n)):
        count += 1
        n_b = b[n_b-1]
        if n_b == 2:
            print(count)
            flag = 1
            break
        elif n_b in b_old:
            print("-1")
            flag = 1
            break
        else:
            b_old.append(n_b)

    if flag == 0:
        print("-1")


### FIXED CODE ###

n = int(input())
b = []
b_old = []
for i in range(n):
    tmp = int(input())
    b.append(tmp)
n_b = 1
count = 0
flag = 0
while(count < n):
    n_b = b[n_b-1]
    count += 1
    if n_b == 2:
        print(count)
        flag = 1
        break
if flag == 0:
    print("-1")
### BUGGY CODE ###

def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
        if not nxt:
            return -1
        for i in set(nxt):
            if A[i]:
                w[i] = A[i].pop()
            else:
                w[i] = -1
                r -= 1
        cur = nxt
    return d


print(main())


### FIXED CODE ###

def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if o == -1:
                continue
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        cur = []
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
                cur.append(i)
            else:
                r -= 1
    return d


print(main())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n,q=map(int,input().split())
G=[[] for i 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)

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

ans=[0]*n

check=[False]*n
temp=0
def dfs(v):
    global temp

    check[v]=True
    temp+=add[v]
    ans[v]=temp

    for next in G[v]:
        if check[next]:
            continue
        dfs(next)
    
    temp-=add[v]

dfs(0)

print(*ans)



### FIXED CODE ###

from collections import deque

N,Q=map(int,input().split())
L=[[] for _ in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
count=[0]*(N+1)
for j in range(Q):
    p,x=map(int,input().split())
    count[p]+=x

#print(count)

q=deque() #queueとして(popleftとappend)
q.append(1)
parent=[-1]*(N+1)
#parent[1]=1

while q:
    now=q.popleft()
    for k in L[now]:
        if parent[now]==k:
            continue
        count[k]+=count[now]
        parent[k]=now
        q.append(k)
        #print(parent)

print(*count[1:])
### BUGGY CODE ###

import numpy as np
N = int(input())
h_array = np.array(list(map(int, input().split()))).reshape(-1)


def cost_diff(num, span, given_array):
    diff_val = np.abs(given_array[num] - given_array[num - span])
    return np.array(diff_val).reshape(-1)


dp = [[] for i in range(N)]
diff_ini = cost_diff(1, 1, h_array)

for i in range(N):
    if i == 0:
        dp[0].append(0)
    elif i == 1:
        dp[1].append(min(dp[0] + diff_ini))
    else:
        tmp_1 = dp[i - 1] + cost_diff(i, 1, h_array)
        tmp_2 = dp[i - 2] + cost_diff(i, 2, h_array)
        tmp = min(tmp_1, tmp_2)
        dp[i].append(int(tmp))
print(dp[N - 1][0])


### FIXED CODE ###

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

dp = [10 ** 5 for i in range(N)]

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = dp[0] + abs(h_array[1] - h_array[0])
    else:
        dp[i] = min(dp[i - 1] + abs(h_array[i] - h_array[i - 1]), dp[i - 2] + abs(h_array[i] - h_array[i - 2]))
print(dp[N - 1])
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
s,t=map(int,input().split())
s-=1
t-=1
q=deque([[s,0]])
v=[0]*n
while q:
    p=q.popleft()
    v[p[0]]=1
    for j in g[p[0]]:
        for j2 in g[j]:
            for j3 in g[j2]:
                if j3==t:
                    print(p[1]+1)
                    exit()
                if v[j3]==0:
                    v[j3]=1
                    q.append([j3,p[1]+1])
print(-1)

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(3*n)]
for i in range(m):
    a,b=map(int,input().split())
    g[3*(a-1)].append(3*(b-1)+1)
    g[3*(a-1)+1].append(3*(b-1)+2)
    g[3*(a-1)+2].append(3*(b-1))
s,t=map(int,input().split())
s-=1
t-=1
s*=3
t*=3
q=deque([[s,0]])
v=[0]*(3*n)
while q:
    p=q.popleft()
    v[p[0]]=1
    for j3 in g[p[0]]:
        if j3==t:
            print((p[1]+1)//3)
            exit()
        if v[j3]==0:
            v[j3]=1
            q.append([j3,p[1]+1])
print(-1)
### BUGGY CODE ###

s = input()
K = int(input())
sub = {s}
for d in range(1,len(s)):
    for i in range(len(s)-d+1):
        sub |= {s[i:i+d]}
print(sorted(sub)[K-1])

### FIXED CODE ###

s = input()
K = int(input())
sub = {s}
for d in range(1,6):
    for i in range(len(s)-d+1):
        sub |= {s[i:i+d]}
sub = list(sub)
n = len(sub)
for i in range(K):
    for j in range(n-i):
        a, b = sub[-i-1], sub[j]
        if a > b: sub[-i-1], sub[j] = b, a
print(sub[-K])
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(N+1)]
    # for i in range(1, L+1):
    # dp[0][0][0] = 0

    # def solve(c1, c2, c3):
    #     if dp[c1][c2][c3] >= 0:
    #         return(dp[c1][c2][c3])
    #     else:
    #         P = 1
    #         if c1 > 0:
    #             P += solve(c1-1, c2, c3) * (c1/N)
    #         if c2 > 0:
    #             P += solve(c1+1, c2-1, c3)*(c2/N)
    #         if c3 > 0:
    #             P += solve(c1, c2+1, c3-1)*(c3/N)
    #         P /= (1 - (N-c1-c2-c3)/N)
    #         dp[c1][c2][c3] = P

    #         return(P)

    # print(solve(A[1], A[2], A[3]))

    for k in range(A[3]+1):
        for j in range(A[2]+A[3] + 1 - k):
            for i in range(A[1]+A[2]+A[3] + 1 - k - j):
                if i == 0 and j == 0 and k == 0:
                    continue
                P = N
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                P /= i+j+k
                dp[i][j][k] = P

    print(dp[A[1]][A[2]][A[3]])


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

s = input()
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = list(input().split())
    if a[0] == "1":
        z += 1
    else:
        if (int(a[1]) + z) % 2 == 0:
            R += a[2]
        else:
            F = a[2] + F
ans = F + s + R
if z%2==0:
    print(ans)
else:
    print(ans[::-1])



### FIXED CODE ###

from collections import deque
d = deque()
d.extend(list(input()))
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = tuple(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            d.append(a[2])
        else:
            d.appendleft(a[2])

ans = "".join(d)
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

a, b, k = map(int, input().split())
l = [i for i in range(a, b+1)]

for i in l[:k]:
    print(i)
for j in l[len(l)-k:]:
    if j <= i:
        continue
    print(j)

### FIXED CODE ###

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

c = a
while c < a + k and c <= b:
    print(c)
    c += 1
c = max(b-k+1, c)
while c <= b:
    print(c)
    c += 1
### BUGGY CODE ###

N,M=map(int,input().split())
*A,=map(int,input().split())
l=[]
for a in A:
    k=a
    while k>=1:
        l+=[k-k//2]
        k=k//2
print(sum(A)-sum(sorted(l)[-M:]))

### FIXED CODE ###

def f():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  print(sum(A)-sum(sorted(l)[-M:]))
if __name__=="__main__":
  f()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 25 17:57:31 2020

@author: Paras
"""

n,k = map(int, input().split())
marks = list(map(int, input().split()))
score_curr = 1
for i in range(k):
  score_curr*=marks[i]
  
f = marks[0]
score_prev = score_curr
j = 0
for i in range(k,n):
    score_curr = (score_prev//f)*marks[i]
    if score_curr>score_prev:
        print("Yes")
    else:
        print("No")
    score_prev = score_curr
    j+=1
    f = marks[j]

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jul 25 17:57:31 2020

@author: Paras
"""

n,k = map(int, input().split())
marks = list(map(int, input().split()))
i = 0
j = i+k
while j<n:
    if marks[j]>marks[i]:
        print("Yes")
    else:
        print("No")
    i+=1
    j+=1
### BUGGY CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
dprint("n, k = ", n, k)

lx = 0
rx = max(A)
ans = 0
while (int(lx) < int(rx)):
    x = (rx + lx) / 2
    dprint("lx, x, rx = ", lx, x, rx)
    n = 0
    for i in range(len(A)):
        n += math.ceil(A[i] / x) - 1
    dprint("n = ", n)
    if n <= k:
        dprint(" smaller x")
        rx = x
        ans = x
    else:
        dprint(" cut less, bigger x")
        lx = x
        ans = rx

ans = math.ceil(ans)
print(ans)


### FIXED CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
dprint("n, k = ", n, k)

lx = int(0)   # NG
rx = int(1e9) # OK
#ans = 0
while ((rx-lx)>1):
    x = (rx + lx) // 2
    dprint("lx, x, rx = ", lx, x, rx)
    n = 0
    for i in range(len(A)):
        #n += math.ceil(A[i] / x) - 1
        n += (A[i]-1) // x
        if n > k: break
    dprint("n = ", n)
    if n <= k:
        dprint(" smaller x")
        rx = x
    else:
        dprint(" cut less, bigger x")
        lx = x

#ans = math.ceil(rx)
print(rx)
### BUGGY CODE ###

N = int(input())
a=list(map(int, input().split()))
Q = int(input())
num_a =[0]*100001
num_b = []
sum_a = sum(a)
b=[]
c=[]
for i in range(Q):
  b1,c1=map(int, input().split())
  b.append(b1)
  c.append(c1)
  if b[i] not in a:
    continue
  elif num_a[b[i]]>0:
    continue
  else:
    num_a[b[i]] = a.count(b[i])
for i in range(Q):
  if num_a[b[i]]==0:
    num_b.append(0)
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  else:
    num_b.append(num_a[b[i]])
    num_a[c[i]] += num_a[b[i]]
    num_a[b[i]] = 0
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  print(sum_a)


### FIXED CODE ###

N = int(input())
a=list(map(int, input().split()))
Q = int(input())
num_a =[0]*100001
num_b = []
sum_a = sum(a)
b=[]
c=[]
for i in a:
  num_a[i]+= 1
for i in range(Q):
  b1,c1=map(int, input().split())
  b.append(b1)
  c.append(c1)
for i in range(Q):
  if num_a[b[i]]==0:
    num_b.append(0)
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  else:
    num_b.append(num_a[b[i]])
    num_a[c[i]] += num_a[b[i]]
    num_a[b[i]] = 0
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  print(sum_a)
### BUGGY CODE ###

S = input()
T = input()
D = [[] for _ in range(26)]
for i in range(26):
  D[i] = [0] * S.count(chr(97 + i))
P = [0] * 26
for i, s in enumerate(S):
  n = ord(s) - 97
  D[n][P[n]] = i + 1
  P[n] += 1
def bsearch(t, pos, loop):
  d = D[ord(t) - 97]
  l = len(d)
  if l < 1:
    return -1, 0
  if pos < d[0]:
    return d[0], loop
  if d[l - 1] <= pos:
    loop += 1
    return d[0], loop
  low = 0
  high = l
  while high - low > 1:
    mid = (high - low) // 2
    if pos < d[mid]:
      high = mid
    else:
      low = mid
  return d[high], loop
pos = 0
loop = 0
for t in T:
  pos, loop = bsearch(t, pos, loop)
  if pos == -1:
    print(-1)
    break
else:
  print(len(S) * loop + pos)

### FIXED CODE ###

import bisect
S = input()
T = input()
D = [[] for _ in range(26)]
for i in range(26):
  D[i] = [0] * S.count(chr(97 + i))
P = [0] * 26
for i, s in enumerate(S):
  n = ord(s) - 97
  D[n][P[n]] = i + 1
  P[n] += 1
pos = 0
loop = 0
for t in T:
  n = ord(t) - 97
  if D[n] == []:
    print(-1)
    break
  _d = bisect.bisect(D[n], pos)
  _pos = D[n][_d % len(D[n])]
  if _pos <= pos:
    loop += 1
  pos = _pos
else:
  print(len(S) * loop + pos)