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

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = [0] * K
    dp[0] = 1
    for i in range(1, N+1):
        for j in range(K-1, -1, -1):
            if i-1 != omit and j-A[i-1] >= 0:
                dp[j] |= dp[j-A[i-1]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

## 種類数の求め方
# 1. A内の要素を取り出して、それがA内に存在するとき：種類＋１
# 2. その要素を重複数だけAから削除してループ

kinds = 0
A.sort()
duplicatedList = []
while len(A) > 0:
    if A[0] in A:
        kinds += 1
        duplicatedList.append(A.count(A[0]))
        for j in range(A.count(A[0])):
            A.remove(A[0])

if kinds <= K:
    print('0')
elif kinds > K:
    duplicatedList.sort()
    tmp = 0
    for i in range(kinds-K):
        tmp += duplicatedList[i]
    print(tmp)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        l[d[a[i]]]+=1
    except:
        d[a[i]]=len(l)
        l.append(1)
ans=0
l.sort()
for i in range(len(l)-k):
    ans+=l[i]
print(ans)
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
f=[False for i in range(max(a)+1)]

ans=0
for i in range(n):
    t=a[i]
    if i!=n-1:
        if f[t]==False and t!=a[i+1]:       
            ans+=1
            while t<=max(a):
                f[t]=True
                t+=a[i]
        elif f[t]==False and t==a[i+1]:
            while t<=max(a):
                f[t]=True
                t+=a[i]
    if i==n-1:
        if f[t]==False:       
            ans+=1

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[0]*(a[-1]+1)

for i in a :
    dp[i]+=1

for i in a :
    if dp[i] :
        for j in range(i*2,a[-1]+1,i) :
            dp[j]=0

print(dp.count(1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Top2:
    def __init__(self,x=-1,y=-1):
        if x<y:x,y=y,x
        self.val=[x,y]
        self.s=x+y

    def __add__(self, other):
        i=j=0
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        self.s=sum(self.val)
        return self

n=II()
aa=LI()
dp=[Top2(a) for a in aa]

for i in range(n):
    for j in range((1<<n)-1,-1,-1):
        if j>>i&1:continue
        dp[j|1<<i]+=dp[j]

mx=-1
for j in range(1,1<<n):
    mx=max(mx,int(dp[j].s))
    print(mx)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Top2:
    def __init__(self,x=-1,y=-1):
        if x<y:x,y=y,x
        self.val=[x,y]
        self.s=x+y

    def __add__(self, other):
        i=j=0
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        self.s=sum(self.val)
        return self

n=II()
aa=LI()
dp=[Top2(a) for a in aa]

for i in range(n):
    for j in range((1<<n)-1,-1,-1):
        if j>>i&1:continue
        dp[j|1<<i]+=dp[j]

mx=-1
for j in range(1,1<<n):
    mx=max(mx,int(dp[j].s))
    print(mx)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
a=list(map(int,input().split()))+[10**10]
edge=[[]for _ in range(n)]
for x,y in[list(map(int,input().split()))for _ in range(n-1)]:
  edge[x-1].append(y-1)
  edge[y-1].append(x-1)
def bfs(r,v):
  return (a[r]<=a[v])|sum(not(bfs(v,i))for i in edge[v] if i!=r)
ans=[]
for i in range(n):
  if bfs(n,i):ans.append(i+1)
print(*ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
a=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for x,y in[list(map(int,input().split()))for _ in range(n-1)]:
  edge[x-1].append(y-1)
  edge[y-1].append(x-1)
def bfs(r,v):
  for i in edge[v]:
    if(r!=i)and(a[v]>a[i])and(not(bfs(v,i))):return True
  return False
print(*[i+1 for i in range(n)if bfs(-1,i)])
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
v = list(map(int, input().split()))
limit = 10 ** 18

answer = 1
if 0 in v:
  answer = 0
else:
  for i in v:
    answer = answer * i
    if answer <= limit:
      continue
    else:
      answer = -1
      break
print(answer)
### BUGGY CODE ###

N = int(input())
A = [ int(i) for i in input().strip().split(' ')]
a = 1
for Ai in A:
    a *= Ai
if a > 10**18:
    print('-1')
else:
    print(a)

### FIXED CODE ###

_ = int(input())
A = [ int(i) for i in input().strip().split(' ')]
a = 1
if min(A) == 0:
    print(0)
else:
    for Ai in A:
        a *= Ai
        if a > 10**18:
            print('-1')
            break
    else:
        print(a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    tmp = []
    tmp.append(year)
    tmp.append(i)
    town[place-1].append(tmp)

ans = []

for item in town:
    index = town.index(item)
    item.sort()
    index += 1
    index = str(index)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = i + 1
        num = str(num)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        tmp = []
        tmp.append(item[i][1])
        tmp.append(xxx)
        ans.append(tmp)

ans.sort()
for item in ans:
    print(item[1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    town[place-1].append([year,i])

# print(town)

ans = []
k = 0
for item in town:
    index = k
    # index = town.index(item)
    # print(item)
    item.sort()
    index = str(index+1)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = str(i+1)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        ans.append([item[i][1],xxx])
    k += 1

ans.sort()
for item in ans:
    print(item[1])
### BUGGY CODE ###

import itertools

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

kumiawase = list(itertools.combinations(a, 2))
ans = 0

for i in range(len(kumiawase)):
  ans += kumiawase[i][0] * kumiawase[i][1]
  
print(ans % (1000000000+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
zenbu = sum(a)
ans = 0

for i in range(n):
  ans += a[i]*(zenbu-a[i])
 
print(ans // 2 % 1000000007)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                color[i][j]="gray"
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
print(BFS())

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"

    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())
### BUGGY CODE ###

P = 998244353

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

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

dp[0][0][0] = 1
dp[0][0][1] = 1
if A[0] <= S:
    dp[0][A[0]][1] = 1

for i in range(1, N):
    dp[i][0][0] = 1
    dp[i][0][1] = dp[i-1][0][1] + 1
    dp[i][S][2] = dp[i-1][S][2] + dp[i-1][S][1]
    if A[i] == S:
        dp[i][S][2] += 1 + dp[i-1][0][1]
        dp[i][S][1] += dp[i-1][0][1] + 1
    elif A[i] < S:
        dp[i][A[i]][1] += 1 + dp[i-1][0][1]
    for j in range(1, S+1):
        dp[i][j][1] += dp[i-1][j][1]
        if j + A[i] < S:
            dp[i][j+A[i]][1] += dp[i-1][j][1]
        elif j + A[i] == S:
            dp[i][S][2] += dp[i-1][j][1]
            dp[i][S][1] += dp[i-1][j][1]
        dp[i][j][0] %= P
        dp[i][j][1] %= P
        dp[i][j][2] %= P

print(dp[N-1][S][2])

### FIXED CODE ###

P = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N)]
dp1 = [[0]*(S+1) for _ in range(N)]
dp2 = [[0]*(S+1) for _ in range(N)]

dp0[0][0] = 1
dp1[0][0] = 1
if A[0] <= S:
    dp1[0][A[0]] = 1

for i in range(1, N):
    dp0[i][0] = 1
    dp1[i][0] = dp1[i-1][0] + 1
    dp2[i][S] = dp2[i-1][S] + dp1[i-1][S]
    if A[i] == S:
        dp2[i][S] += dp1[i-1][0] + 1
        dp1[i][S] += dp1[i-1][0] + 1
    elif A[i] < S:
        dp1[i][A[i]] += 1 + dp1[i-1][0]
    for j in range(1, S+1):
        dp1[i][j] += dp1[i-1][j]
        if j + A[i] < S:
            dp1[i][j+A[i]] += dp1[i-1][j]
        elif j + A[i] == S:
            dp2[i][S] += dp1[i-1][j]
            dp1[i][S] += dp1[i-1][j]
        dp0[i][j] %= P
        dp1[i][j] %= P
        dp2[i][j] %= P

print(dp2[N-1][S])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z=DD.count(0)*u
  a_n=x+sum(DD)*u
  for i in range(v):
    a_n+=DD[i]
    if DD[i]==0:
      z+=1
  ans-=z+a_n//m
  print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z1,z2,r,s=0,0,0,0
  for i,d in enumerate(DD):
    s+=d
    if i<v:
      r+=d
      if d==0:
        z1+=1
        z2+=1
    elif d==0:
      z2+=1
  ans-=(z2*u+z1)+(x+s*u+r)//m
  print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(n-1):
    ans += A[i]*sum(A[i+1:])
    ans %= 1000000007

print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
total = sum(A[1:])

for i in range(n-1):
    ans += A[i]*total
    total -= A[i+1]
    ans %= 1000000007

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

n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

count = 0


for c in C:
    for b in filter(lambda x: x<c ,B):
        saidan = filter(lambda x: x<b ,A)
        count+=len(list(saidan))
                
print(count)

### FIXED CODE ###

import bisect
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    a.sort()
    b.sort()
    c.sort()
    ans = 0
    for y in b:
        i = bisect.bisect_left(a, y)
        j = bisect.bisect_right(c, y)
        if i > 0 and j != len(c):
            ans += i * (n - j)
 
    print(ans)
 
main()
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
ans=0
for i in range(1,n+1):
    tmp=math.floor(a*i/b)- a*math.floor(i/b)
    ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

a,b,n = map(int,input().split())
x=min(b-1,n)
ans=a*x//b-a*(x//b)
print(ans)
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
  s.append("".join(sorted(input())))
s.sort()
sss=set(s)
ans=0
for _ in sss:
  l=s.count(_)
  ans+=l*(l-1)//2
print(ans)

### FIXED CODE ###

n=int(input())
s=[]
for i in range(n):
  s.append("".join(sorted(input())))
#sss=set(s)
ans=0
import collections
c=collections.Counter(s)

for l in c.values():
  ans+=l*(l-1)*(1/2)
print(int(ans))
### BUGGY CODE ###

import numpy as np
n = int(input())
mod = 10 ** 9 + 7
a = [list(bin(int(i))[2:].zfill(60)) for i in input().split()]
a = np.array(a)
x = a.T
x = x.tolist()
#print(x)
ans = 0
for i in range(60):
    y = x[i].count('0')
    z = x[i].count('1')
    tmp = ( (n * (n - 1) // 2) - (y * (y - 1) // 2) - (z * (z - 1) // 2) ) % mod
    tmp2 = 1
    for j in range(60 - i - 1):
        tmp2 = tmp2 * 2 % mod
    #print(tmp,tmp2)
    
    ans = (ans + tmp2 * tmp) % mod
print(ans)
    
    

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
mod = 10 ** 9 + 7
ans = 0
m = 1
for _ in range(60):
    bit = sum(a & m for a in x) #フラグが立ってる桁を合計
    bit //= m #1の個数を数えるためにmで割る
    non_bit = n - bit #0の個数を出す
    ans = (ans + bit * non_bit * m) % mod #桁の合計出す
    m <<= 1 #桁を1増やす
print(ans)
### BUGGY CODE ###

def solve():
    s = list(input())

    t = ''.join(s)
    cnt = 0
    while 'BW' in t:
        for i in range(len(s)-1):
            if s[i] == 'B' and s[i+1] == 'W':
                s[i], s[i+1] = 'W', 'B'
                cnt += 1
        t = ''.join(s)

    return cnt

if __name__ == "__main__":
    print(solve())



### FIXED CODE ###

def solve():
    s = list(input())

    cnt = 0
    for i in range(len(s)):
        if s[i] == 'W':
            cnt += i

    w = s.count('W')
    a = [int(i) for i in range(w)]
    cnt -= sum(a)

    return cnt

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

N,P = map(int,input().split())
i = round(P**(1/N))
j = 2
res = 1
if N == 1:
  print(P)
elif P == 1|N>=40:
  print(1)
else:
  while P%(j**N)==0:
    P = P//(j**N)
    res *= j
  j += 1
  for f in range(j,i+1,2):
    while P%(f**N) == 0:
      P = P//(f**N)
      res *= f
      
  print(res)

### FIXED CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  for i in range(i,0,-1):
    if P%i**N==0:
      print(i)
      break
### BUGGY CODE ###

import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M
 
for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  #X[m] = X[m] + [a] + [b]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        break
      else:
        #XX.append(x + [v[1]])
        XX[i] = x + [v[1]]
        i += 1
    X = [x for x in XX if x]


if ans == []:
  print(-1)
else:
  ans[0] = [len(ans[0])-1] + ans[0]
  print(*ans[0][:-1])

### FIXED CODE ###

def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()
### BUGGY CODE ###

dummy = list(map(int, input().split(" ")))
N = dummy[0]

P = list(map(int, input().split(" ")))

out = 0
for a in range(N):
    flag = 1
    for b in range(a + 1):
        #print(P[a], P[b])
        if(P[a] > P[b]):
            flag = 0
            break
    if(flag == 1):
        out += 1

#print(P)
print(out)

### FIXED CODE ###

dummy = list(map(int, input().split(" ")))
N = dummy[0]

P = list(map(int, input().split(" ")))

out = 0
min = N + 1
for a in range(N):
    if(P[a] <= min):
        min = P[a]
        out += 1

#print(P)
print(out)
### BUGGY CODE ###

n=int(input())
lisa=[]
ans=0
for i in range(n):
    a=input()
    lisa.append(a)
    if ans<lisa.count(a):
        ans=lisa.count(a)
add=[]
for i in range(n):
    if lisa.count(lisa[i])==ans:
        add.append(lisa[i])
add=sorted(list(set(add)))
for i in range(len(add)):
    print(add[i])

### FIXED CODE ###

n=int(input())
S=[]
ans=0
import collections
for i in range(n):
    s=input()
    S.append(s)
S=sorted(S)
c=collections.Counter(S)
ANS=[]
for i in range(n-1):
    if (S[i]!=S[i+1] and ans<c[S[i]]) or i==n-2:
        ans=c[S[i]]#Sの？番目がSにいくつあるのか
        ANS.append(ans)
inko=""
ans=max(ANS)
for i in range(n):
    if c[S[i]]==ans and S[i]!=inko:
        print(S[i])
        inko=S[i]
### BUGGY CODE ###

n,m=map(int,input().split())
lr=[]
result=0
gates=0
for i in range(m):
  lr.append(input().split())
#print(lr[0])
for k in range(1,n+1):
  gates=0
  for h in range(m):
    if int(k)>=int(lr[h][0]) and int(k)<=int(lr[h][1]):
      gates+=1
  #print(gates,k)
  if gates==m:
    result+=1
    gates=0
    #print('ID')
print(result)

### FIXED CODE ###

n,m=map(int,input().split())
l=1
r=n
lr=[]
for i in range(m):
  lr.append(input().split())
for j in lr:
  if l<int(j[0]):
    l=int(j[0])
  if r>int(j[1]):
    r=int(j[1])
if r>=l:
  print(int(r-l+1))
else:
  print(0)
### BUGGY CODE ###

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

num = 1

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

for i in range(N):
    B = A[:]
    B.pop(i)
    gcd1 = int(B[0])

    for j in range(1, N-1):
        gcd1 = gcd(gcd1, B[j])

    if num < gcd1:
        num = gcd1

print(num)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []


def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

gcd_list.append(A[0])
reverse_gcd_list.append(A[-1])

for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))
    # reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))
    reverse_gcd_list.append(gcd(reverse_gcd_list[-1], A[-1-i]))

reverse_gcd_list.reverse()
num = [gcd_list[-2], reverse_gcd_list[1]]
for i in range(N-2):
    num.append(gcd(gcd_list[i], reverse_gcd_list[i+2]))

print(max(num))
### BUGGY CODE ###

import numpy as np
n = map(int,input().split())
a = list(map(int,input().split()))
Q = int(input())

list_a = np.array(a)
#print(list_a)

for q in range(Q):
    num = list(map(int,input().split()))
    list_a = np.where(list_a == num[0] ,num[1],list_a)

    print((sum(list_a))  )

### FIXED CODE ###

"""
import numpy as np
from collections import Counter

n = map(int,input().split())
a = list(map(int,input().split()))
Q = int(input())
a_count = dict(Counter(a))



def change_dict_key(d, old_key, new_key, default_value=None):
    d[new_key] = d.pop(old_key, default_value)


#change_dict_key(a_count, 1, 5)

#print(a_count)



for q in range(Q):
    num = list(map(int,input().split()))
    
    if(num[0] not in a_count):
        print(np.dot( np.array(list(a_count.keys())) , np.array(list(a_count.values()) ) ) )
        continue

    if(num[1] not in a_count):
        change_dict_key(a_count,num[0],num[1])

    else :
        a_count[num[1]] += a_count[num[0]] 
        del a_count[num[0]] 
    
    #print(a_count.values())

    print(np.dot( np.array(list(a_count.keys())) , np.array(list(a_count.values()) ) ) )
    #print((sum(list_a))  )
"""
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

B, C = [0]*Q, [0]*Q
for i in range(Q):
    B[i], C[i] = list(map(int, input().split()))

bucket = [0]*100001
for i in A:
    bucket[i] += 1

sum = sum(A)

for i in range(Q):
    sum += (C[i] - B[i]) * bucket[B[i]]
    bucket[C[i]] += bucket[B[i]]
    bucket[B[i]] = 0
    print(sum)