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

import sys
input=sys.stdin.readline
s=tuple(input())
t=tuple(input())
n=len(s)
m=len(t)
dp=[['' for i in range(m+1)] for j in range(n+1)]
#dps=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            #dps[i+1][j+1]=dps[i][j]+1
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
                #dps[i+1][j+1]=dps[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
                #dps[i+1][j+1]=dps[i][j+1]
print(dp[n][m])


### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

multi_child = [[] for i in range(N)]
for i in range(N):
    multi_child[i].append(i)
    v = parent[i]
    while v != -1:
        multi_child[v].append(i)
        v = parent[v]


# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    for v in multi_child[p]:
        count[v] += x
    
print(' '.join(map(str, count)))

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)


## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x
    
deq = deque([0])
while deq:
    v = deq.popleft()
    for w in child[v]:
        count[w] += count[v]
        deq.append(w)



print(' '.join(map(str, count)))
### BUGGY CODE ###

import re

S=input()
S_int = int(S)
interval = 2019
current = 2019
A=[]
for i in range(len(S)):
  for j in range(i+4,len(S)+1):
    if int(S[i:j])%2019 == 0:
      A.append([i+1,j])
print(len(A))

### FIXED CODE ###

S=input()
dp = {0:1}

p=0
q=1

for i in range(len(S)-1,-1,-1):
  p += (int(S[i])*q)
  p = p%2019
  q *= 10
  q = q%2019
  if p not in dp:
    dp[p]=0
  dp[p]+=1

#print(dp)
c = 0
for v in dp:
  c += dp[v]*(dp[v]-1)//2
print(c)
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[0]*(s+1) for _ in range(n+1)]
ans=0
for i in range(n):
  a=A[i]
  if a<s:
    B[i+1][a]+=i+1
  elif a==s:
    B[i+1][a]+=(i+1)*(n-i)
  for j in range(s+1):
    if j<=s:
      B[i+1][j]+=B[i][j]
    if 0<=j-a and j<s:
      B[i+1][j]+=B[i][j-a]
    if 0<=j-a and j==s:
      B[i+1][j]+=B[i][j-a]*(n-i)
    B[i+1][j]%=mod
print(B[n][s])

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[0]*(s+1) for _ in range(n+1)]
ans=0
for i in range(n):
  a=A[i]
  if a<s:
    B[i+1][a]+=i+1
  elif a==s:
    B[i+1][a]+=(i+1)*(n-i)
  for j in range(s+1):
    if j<=s:
      B[i+1][j]+=B[i][j]
    if 0<=j-a and j<s:
      B[i+1][j]+=B[i][j-a]
    if 0<=j-a and j==s:
      B[i+1][j]+=B[i][j-a]*(n-i)
    B[i+1][j]%=mod
print(B[n][s])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += gcd(a, b, c)
print(sum)

### FIXED CODE ###

k = int(input())

ans = [
1,
9,
30,
76,
141,
267,
400,
624,
885,
1249,
1590,
2208,
2689,
3411,
4248,
5248,
6081,
7485,
8530,
10248,
11889,
13687,
15228,
17988,
20053,
22569,
25242,
28588,
31053,
35463,
38284,
42540,
46581,
50893,
55362,
61824,
65857,
71247,
76884,
84388,
89349,
97881,
103342,
111528,
120141,
128047,
134580,
146316,
154177,
164817,
174438,
185836,
194157,
207927,
218812,
233268,
245277,
257857,
268182,
288216,
299257,
313635,
330204,
347836,
362973,
383709,
397042,
416448,
434025,
456967,
471948,
499740,
515581,
536073,
559758,
583960,
604833,
633651,
652216,
683712,
709065,
734233,
754734,
793188,
818917,
846603,
874512,
909496,
933081,
977145,
1006126,
1041504,
1073385,
1106467,
1138536,
1187112,
1215145,
1255101,
1295142,
1342852,
1373253,
1422195,
1453816,
1502376,
1553361,
1595437,
1629570,
1691292,
1726717,
1782111,
1827492,
1887772,
1925853,
1986837,
2033674,
2089776,
2145333,
2197483,
2246640,
2332104,
2379085,
2434833,
2490534,
2554600,
2609625,
2693919,
2742052,
2813988,
2875245,
2952085,
3003306,
3096024,
3157249,
3224511,
3306240,
3388576,
3444609,
3533637,
3591322,
3693924,
3767085,
3842623,
3912324,
4027884,
4102093,
4181949,
4270422,
4361548,
4427853,
4548003,
4616104,
4718640,
4812789,
4918561,
5003286,
5131848,
5205481,
5299011,
5392008,
5521384,
5610705,
5739009,
5818390,
5930196,
6052893,
6156139,
6239472,
6402720,
6493681,
6623853,
6741078,
6864016,
6953457,
7094451,
7215016,
7359936,
7475145,
7593865,
7689630,
7886244,
7984165,
8130747,
8253888,
8403448,
8523897,
8684853,
8802826,
8949612,
9105537,
9267595,
9376656,
9574704,
9686065,
9827097,
9997134,
10174780,
10290813,
10493367,
10611772,
10813692
]

print(ans[k-1])
### BUGGY CODE ###

import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min_(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min_(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()

### FIXED CODE ###

import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
  
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()
### BUGGY CODE ###

N = int(input())
K = int(input())
ans = 0
for i in range(1,N+1):
    s = str(i).count("0")
    l = len(str(i))-s
    if l==K:
        ans+=1
print(ans)


### FIXED CODE ###

from math import factorial as f
from functools import reduce
def C(n,k):
    a,b=sorted((k,n-k))
    return reduce(int.__mul__, range(b+1,n+1),1) // f(a)

def almost_everywhere_zero(v, k):
    if not v or not k: return 0
    s = str(v)
    n,d = len(s), int(s[0])
    
    if k>n: return 0
    
    below = 9**k * C(n-1,k) if n>k else 0
    return below + ( d if k==1 else (d-1) * 9**(k-1) * C(n-1,k-1) + almost_everywhere_zero(int(s[1:]), k-1) )
N = input()
K = int(input())
print(almost_everywhere_zero(N,K))
### BUGGY CODE ###

from collections import deque

Y, X = map(int,input().split())
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
sy,sx = 1,1
gy,gx = Y,X
s = [["#"]*(X+2) for _ in range(Y+2)]
for y in range(Y):
    s[y+1] = list("#"+input()+"#")
inf = Y*X
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
drs = [(-1,0),(1,0),(0,-1),(0,1)]
q = deque([(sy-1, sx-1)])

while q:
    y,x = q.pop()
    cost = c[y][x]
    for dx,dy in drs:
        x2 = x+dx
        y2 = y+dy
        if s[y2+1][x2+1] == "." and c[y2][x2] > cost:
            c[y2][x2] = cost+1
            q.appendleft((y2,x2))
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    dots = 0
    for s1 in s:
        dots +=s1.count(".")
    print(dots-c[gy-1][gx-1]-1)

### FIXED CODE ###

H, W = map(int,input().split())
c = [["#"]*(W+2) for _ in range(H+2)]
dots = 0
for y in range(H):
    c[y+1] = "#",*list(input()),"#" 
    dots += c[y+1].count(".")
inf = H*W
m = [[inf]*W for _ in range(H)]
m[0][0] = 0
drs = [[-1,0],[1,0],[0,-1],[0,1]]

s = 0
yx = [[1, 1]]
notgoal = True
while notgoal and yx:
    yx2 = []
    s += 1
    for y,x in yx:
        for dy, dx in drs:
            x2 = x+dx
            y2 = y+dy
            if c[y2][x2] == "." and m[y2-1][x2-1] == inf:
                m[y2-1][x2-1] = s
                if (y2,x2) == (H,W):
                    notgoal = False
                else:
                    yx2.append([y2, x2])
    yx = yx2

if notgoal:
    print("-1")
else:
    print(dots-s-1)
### BUGGY CODE ###

import sys
A,B = map(int,input().split())
answer = 1 #１で割ることは絶対に可能
if A%2 == 0 and B%2 == 0:
    answer += 1

if min(A,B) == 2:
    print(answer)
    sys.exit(0)
sosuu = [2]
A = min(A,B)
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        if A%L == 0 and B%L == 0:
            answer += 1
print(answer)


### FIXED CODE ###

import sys
A,B = map(int,input().split())
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

A = set(trial_division(A))
B = set(trial_division(B))
print(len(A & B)+1)
### BUGGY CODE ###

def f(As, M):
    prev = None
    c = 0

    for i, A in enumerate(As):
        A %= M
        if i == 0:
            prev = {A: 1}
            if A == 0:
                c += 1
            continue

        ccc = {A: 1}
        for k in prev.keys():
            v = prev[k]
            newv = (k + A) % M
            if newv in ccc:
                ccc[newv] += v
            else:
                ccc[newv] = v
        c += ccc[0] if 0 in ccc else 0
        prev = ccc
    return c


def main():
    N, M = [int(a) for a in input().split()]
    As = [int(a) for a in input().split()]
    print(f(As, M))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# def f(As, M):
#     prev = None
#     c = 0
#
#     for i, A in enumerate(As):
#         A %= M
#         if i == 0:
#             prev = {A: 1}
#             if A == 0:
#                 c += 1
#             continue
#
#         ccc = {A: 1}
#         for k in prev.keys():
#             v = prev[k]
#             newv = (k + A) % M
#             if newv in ccc:
#                 ccc[newv] += v
#             else:
#                 ccc[newv] = v
#         c += ccc[0] if 0 in ccc else 0
#         prev = ccc
#     return c
def f(As, M):
    totals = [As[0] % M]
    res = 1 if As[0] % M == 0 else 0
    for A in As[1:]:
        l = (totals[-1] + A) % M
        if l == 0:
            res += 1
        totals.append(l)

    # N = len(As)

    ddd = {}
    for t in totals:
        if t not in ddd:
            ddd[t] = 0
        res += ddd[t]
        ddd[t] += 1

    # for i in range(N):
    #     ii = totals[N - 1 - i]
    #     if ii == 0:
    #         res += 1
    #     for j in range(i + 1, N):
    #         jj = totals[N - 1 - j]
    #
    #         if jj == ii:
    #             res += 1
    return res


def main():
    N, M = [int(a) for a in input().split()]
    As = [int(a) for a in input().split()]
    print(f(As, M))


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

N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K

c= [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  c[A[i]-1][B[i]-1]=0
  c[B[i]-1][A[i]-1]=0
for k in range(N):
  c[k][k]=0
  
#print(c)

#ワーシャルフロイト法
for k in range(N):
    for i in range(N):
        for j in range(N):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
            
for i in range(M):
  c[A[i]-1][B[i]-1]=float("inf")
  c[B[i]-1][A[i]-1]=float("inf")
            
for j in range(K):
  C[j],D[j]= map(int,input().split())
  c[C[j]-1][D[j]-1]=float("inf")
  c[D[j]-1][C[j]-1]=float("inf")

import collections  
for p in range(N):
  d=collections.Counter(c[p])
  print(d[0]-1)

### FIXED CODE ###

def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  roots[x]=x
  
  while len(v)>0:
    a=v.popleft()
    roots[a]=x
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)

          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト
roots= [ -1 for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
fr_set= [set(fr[i]) for i in range(N)]
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      
      
ans=[0 for _ in range(N)]      
for i in range(N):
  ans[i]= size[i]-1 - len(fr[i])
  for j in bl[i]:
    if roots[j]==roots[i]:
      ans[i] -= 1      
      
print(*ans)
### BUGGY CODE ###



# 素数一覧を作成
primes = [ i for i in range(2, 100001) ]

for i in range(100001):
    for j in range(i+1, 100001):
        try:
            if primes[j] % primes[i] == 0:
                primes.pop(j)
        except IndexError:
            break

# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for prime in primes:
    primetable[prime] = 1

# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2]:
        like2017table[i] = 1

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

for query in queries:
    begin = query[0]
    end = query[1]
    ans = sum(like2017table[begin:end+1])
    print(ans)


### FIXED CODE ###

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, math.ceil(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True


# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if is_prime(i):
        primetable[i] = 1

# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2] == 1:
        like2017table[i] = 1

# 累積和を計算する
cumsum = [ 0 for i in range(100001) ]
currentSum = 0
for i in range(2, 100001):
    currentSum += like2017table[i]
    cumsum[i] = currentSum

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

for query in queries:
    begin = query[0]
    end = query[1]
    ans = cumsum[end] - cumsum[begin-1]
    print(ans)
### BUGGY CODE ###

a,b,k = [int(i) for i in input().split()]
jougen = a+k-1
kagen = b-k+1
for i in range(a,b+1):
  if i<=jougen or kagen<=i:
    print(i)

### FIXED CODE ###

a,b,k = [int(i) for i in input().split()]
jougen = a+k-1
kagen = b-k+1

if jougen>=kagen:
  for i in range(a,b+1):
    print(i)
    
else:
  for i in range(a,jougen+1):
    print(i)
  for i in range(kagen,b+1):
    print(i)
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_p = list(map(float, input().split()))

    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]

    # 初期条件
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += dp[i][j] * lst_p[i]
            dp[i+1][j] += dp[i][j] * (1.0 - lst_p[i])
    
    ans = sum(dp[N][(N//2+1):])

    print(ans)

main()

### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_p = list(map(float, input().split()))

    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]

    # 初期条件
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += dp[i][j] * lst_p[i]
            dp[i+1][j] += dp[i][j] * (1.0 - lst_p[i])
    
    ans = 0
    for i in range((N+1)//2, N+1):
        ans += dp[N][i]

    print(ans)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = a.copy()
from math import gcd

def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                
    return prime

primes = sieve(1000)
flg = True
for x in primes:
    tmp = 0
    for i in range(n):
        if a[i] % x == 0:
            tmp += 1
        while a[i] % x == 0:
            a[i] //= x
    if tmp > 1:
        flg = False

from collections import Counter
cnt = Counter(a)
for x, c in cnt.items():
    if x != 1 and c > 1:
        flg = False

if flg:
    print('pairwise coprime')
else:
    tmp = b[0]
    for i in range(1, n):
        tmp = gcd(tmp, b[i])
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import sys
input = sys.stdin.readline

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    for x in res:
        set_primes.add(x)
        
if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

def prime(n): # nまでの素数を列挙
    import math
    if n == 1:
        return []
    else:
        num_list = [i + 1 for i in range(2,n,2)]
        list_prime = [2]
        limit = math.sqrt(n)
        if n == 2:
            return list_prime
        else:
            while True:
                p = num_list[0]
                if p >= limit:
                    return list_prime + num_list
                list_prime.append(p)
                num_list = [num for num in num_list if num % p != 0]


def primeFactorization(n):
    import math
    if n == 1:
        return {}
    else:
        list_prime = prime(int(math.sqrt(n)))
        i = 0
        dict_pF = {}
        dict_primeFactorization = {}
        for pri in list_prime:
            dict_pF[pri] = 0
        while True:
            if n == 1:
                for key, value in dict_pF.items():
                    if value != 0:
                        dict_primeFactorization[key] = value
                return dict_primeFactorization
            elif i >= len(list_prime):
                dict_pF[n] = 1
                for key, value in dict_pF.items():
                    if value != 0:
                        dict_primeFactorization[key] = value
                return dict_primeFactorization
            p = list_prime[i]
            if n % p == 0:
                n //= p
                dict_pF[p] += 1
                continue
            else:
                i += 1

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

ans = 0
for number in list_a:
    try:
        ans += primeFactorization(number)[2]
    except:
        pass

print(ans)


### FIXED CODE ###

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

factor2 = 0
for number in list_a:
    while number % 2 == 0:
        number /= 2
        factor2 += 1

print(factor2)
### BUGGY CODE ###

from sys import stdin

def main():
    n = int(input())
    a = [int(x) for x in stdin.readline().rstrip().split()]
    q = int(input())
    for i in range(q):
        b, c = [int(x) for x in stdin.readline().rstrip().split()]
        a = [c if x == b else x for x in a]
        print(sum(a))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

mapping = [0] * 100001

def main():
    n = int(input())
    a = [int(x) for x in stdin.readline().rstrip().split()]
    base = sum(a)
    for aaa in a:
        mapping[aaa] += 1
    q = int(input())
    for i in range(q):
        b, c = [int(x) for x in stdin.readline().rstrip().split()]
        offset = c - b
        kazu = mapping[b]
        base = base + kazu*offset
        mapping[b] = 0
        mapping[c] += kazu
        
        print(base)
        

if __name__ == "__main__":
    main()