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

def solve(n, alist, s):
    senkei=[0]
    answer=0
    for i in range(n):
        teban=s[n-i-1]
        now=alist[n-i-1]
        if teban=='0':
            if now in senkei:
                pass
            else:
                new=[]
                for sn in senkei:
                    new.append(sn^now)
                senkei+=new
        else:
            if now in senkei:
                pass
            else:
                answer=1
    return answer

t=int(input())
for i in range(t):
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))

### FIXED CODE ###

def kosu(kitei, aaa, tuika):
    global now_ret
    ret = 0
    n=len(kitei)
    ret2=0
    kitei.append(aaa)
    n+=1
    for i in range(n):
        if kitei[i]:
            ret2 += 1
            x = 0
            while (2**(x+1)) <= kitei[i]:
                x += 1
            for y in range(i+1, n, 1):
                if kitei[y] & (2 ** x):
                    kitei[y] ^= kitei[i]
    
    if now_ret==ret2:
        return 1
    else:
        if tuika==1:
            now_ret+=1
        return 0
 
 
def solve(n, alist, s):
    kitei=[0]
    answer=0
    for i in range(n):
        teban=s[n-i-1]
        now=alist[n-i-1]
        if teban=='0':
            if kosu(kitei, now, 1)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now, 0)>0:
                pass
            else:
                answer=1
        #print(kitei)
    return answer
 
t=int(input())
for i in range(t):
    now_ret=0
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))
### BUGGY CODE ###

n = int(input())

l = [i for i in range(n)]

print(sum(l))

### FIXED CODE ###

n = int(input())

print((n-1) * (n - 1 + 1) // 2)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
def main():
    N,M=map(int, input().split())
    l =[set() for _ in range(N)]
    for _ in range(M):
        a,b=map(int, input().split())
        for s in l:
            if s:
                if a in s or b in s:
                    s.add(a)
                    s.add(b)
                    break
            else:
                s.add(a)
                s.add(b)
                break
    ans=-1
    for s in l:
        if not(s):
            break
        ans=max(ans,len(s))
    if ans==-1:
        print(1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents=[-1 for _ in range(n)]
    
    def find(self,n):
        x=self.parents[n]
        if x<0:
            return n
        else:
            self.parents[n]=self.find(self.parents[n])
            return self.parents[n]
    
    def union(self,n,m):
        x=self.find(n)
        y=self.find(m)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x

sys.setrecursionlimit(10**9)    
n,m=map(int,input().split())
uf=UnionFind(n)

for _ in range(m):
    a,b=map(lambda x: int(x)-1, input().split())
    uf.union(a,b) 

ans=0

for p in uf.parents:
    ans=min(ans,p)

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

from collections import defaultdict

N, K, L = [int(a) for a in input().split(" ")]
P, Q = zip(*[[int(v) for v in input().split(" ")] for i in range(K)])
R, S = zip(*[[int(v) for v in input().split(" ")] for i in range(L)])

def find(tab, a):
    if tab[a] == -1: return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

loads = [-1]*N
rails = [-1]*N
for p, q in zip(P, Q):
    union(loads, p-1, q-1)

for r, s in zip(R, S):
    union(rails, r-1, s-1)

dl = defaultdict(set)
dr = defaultdict(set)
for i in range(N):
    dl[find(loads, i)].add(i)
    dr[find(rails, i)].add(i)

ans = [len(dl[find(loads, i)].intersection(dr[find(rails, i)])) for i in range(N)]

print(" ".join([str(n) for n in ans]))


### FIXED CODE ###

from collections import defaultdict

N, K, L = [int(a) for a in input().split(" ")]
P, Q = zip(*[[int(v) for v in input().split(" ")] for i in range(K)])
R, S = zip(*[[int(v) for v in input().split(" ")] for i in range(L)])

def find(tab, a):
    if tab[a] == -1: return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

loads = [-1]*N
rails = [-1]*N
both = [-1]*N
for p, q in zip(P, Q):
    union(loads, p-1, q-1)

for r, s in zip(R, S):
    union(rails, r-1, s-1)

dic = defaultdict(lambda: 0)
ans = []
for i in range(N):
    key = (find(loads, i), find(rails, i))
    ans.append(key)
    dic[key] += 1

ans = [dic[key] for key in ans]
print(" ".join([str(cnt) for cnt in ans]))
### BUGGY CODE ###

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

N = get[0]
K = get[1]
Q = get[2]

point = [K]*N
list = [0]*N

for i in range(Q):
  A = input()
  list.append(int(A))

for i in range(N):
  if point[i] - (Q - list.count(i+1)) > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

N = get[0]
K = get[1]
Q = get[2]

list = [0]*N

for i in range(Q):
  list[int(input()) - 1] += 1 

for i in range(N):
  if K - (Q - list[i]) > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n=int(input())
a=list(list(map(int,input().split())))
for i in range(n):
    a[i]-=i
ans=0
for i in range(n-1):
    h=-(a[i]+2*i)
    ans+=a[i+1:].count(h)
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(list(map(int,input().split())))
ma=[i-a[i] for i in range(n)]
r=Counter(ma)
ans=0
for i in range(n):
    ans+=r[i+a[i]]
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def main():
    cnt = [[0] * W for _ in range(H)]
    for h in range(H):
        done = [0] * W
        for w in range(W):
            if S[h][w] == '#' or done[w] == 1:
                continue
            c = 0
            while W > w + c:
                if S[h][w + c] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h][w + k] += c
                done[w + k] = 1
    for w in range(W):
        done = [0] * H
        for h in range(H):
            if S[h][w] == '#' or done[h] == 1:
                continue
            c = 0
            while H > h + c:
                if S[h + c][w] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h + k][w] += c
                done[h + k] = 1
    ans = 0
    for r in cnt:
        for c in r:
            ans = max(ans, c - 1)
    print(ans)


main()


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def main():
    cnt = [[0] * W for _ in range(H)]
    for h in range(H):
        done = [0] * W
        for w in range(W):
            if S[h][w] == '#' or done[w] == 1:
                continue
            c = 0
            while W > w + c:
                if S[h][w + c] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h][w + k] += c
                done[w + k] = 1
    for w in range(W):
        done = [0] * H
        for h in range(H):
            if S[h][w] == '#' or done[h] == 1:
                continue
            c = 0
            while H > h + c:
                if S[h + c][w] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h + k][w] += c
                done[h + k] = 1
    ans = 0
    for r in cnt:
        for c in r:
            ans = max(ans, c - 1)
    print(ans)


main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = [int(input()) for i in range(n)]

cnt = Counter(a)
for i in range(n):
  temp = cnt.copy()
  temp[a[i]] -= 1
  if temp[a[i]] == 0:
    del temp[a[i]]

  print(max(temp.keys()))




### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(input()) for i in range(n)]

cnt = Counter(a)
maxs = sorted(list(set(a)))[::-1]
for ai in a:
  if ai == maxs[0]:
    if cnt[ai] > 1:
      print(ai)
    else:
      print(maxs[1])
  else:
    print(maxs[0])
### BUGGY CODE ###

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

for query_i in query:
    t = query_i[ 0 ]
    if t == "1":
        s = s[::-1]
    else:
        f = query_i[ 1 ]
        c = query_i[ 2 ]
        if f == "1":
            s = str( c ) + s
        else:
            s = s + str( c )

print( s )

### FIXED CODE ###

s = [ str( input() ) ]
q = int( input() )
query = []
rev_flag_k = 0
for _ in range( q ):
    query_i = list( input().split() )
    query.append( query_i )
    if query_i[ 0 ] == "1":
        rev_flag_k += 1

top = []
rev_flag = 0
for query_i in query:
    t = query_i[ 0 ]
    if t == "1":
        rev_flag += 1
    else:
        f = query_i[ 1 ]
        c = query_i[ 2 ]
        if f == "1" and rev_flag % 2 == 1:
            s.append( str( c ) )
        elif f == "2" and rev_flag % 2 == 0:
            s.append( str( c ) )
        else:
            top.append( str( c ) )
s = "".join( top )[::-1] + "".join( s )
if rev_flag_k % 2 == 1:
    s = s[::-1]

print( s )
### BUGGY CODE ###

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

h, w = map(int, input().split())
a = [[j == "#" for j in input()] for _ in range(h)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# スタート地点をqueueに追加
que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0
add = 0
while True:
    count += 1
    loop += add
    add = 0
    nque = deque()
    while que:
        y, x = que.popleft()
        add -= 1
        for j in range(4):
            ny = y + dy[j]
            nx = x + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                nque.append((ny, nx))
                add += 1
    if nque:
        que = copy.copy(nque)
    else:
        break

print(count - 1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


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

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k=nm()
a=nl()
b=[1]*(n+1)

for i in range(n):
  b[i+1] = a[i]*b[i]

for i in range(n-k):
  if b[i+k+1]//b[i+1] > b[i+k]//b[i]:
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

from math import log10

n,k=nm()
a=nl()
b=[1]*(n+1)

for i in range(n):
  b[i+1] = log10(a[i])+b[i]

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

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

m = []
count = 0
for i in range(n):
    li = p[:i+1]
    li.sort()
    m.append(li[0])
    if m[i] == p[i]:
        count += 1
        
print(count)

### FIXED CODE ###

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

m = p[0]
count = 1
for i in range(1,n):
    if m >= p[i]:
        m = p[i]
        count += 1
        
print(count)
### BUGGY CODE ###

n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,w+1):
        if wt[i-1]<=j:
            dp[i][j]=max(value[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])


### FIXED CODE ###

n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
dp=[[0 for i in range(sum(value)+1)] for j in range(n+1)]
for i in range(sum(value)+1):
    dp[0][i]=1000000000000
for j in range(n+1):
    dp[j][0]=0
for i in range(1,n+1):
    for j in range(1,sum(value)+1):
        if value[i-1]<=j:
            dp[i][j]=min(wt[i-1]+dp[i-1][j-value[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(sum(value),-1,-1):
    if dp[-1][i]<=w:
        print(i)
        break
### BUGGY CODE ###

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst = [[int(s) for s in input().split()]] + lst
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

### FIXED CODE ###

n, m = map(lambda x: int(x), input().split())
drinks = []
for _ in range(n):
    a, b = map(lambda x: int(x), input().split())
    drinks.append((a, b))
    
sorted_drinks = sorted(drinks, key=lambda x: x[0])

num_drinks = 0
sum_prices = 0
for price, num in sorted_drinks:
    num_drinks += num
    sum_prices += num * price
    if num_drinks > m:
        sum_prices -= (num_drinks - m) * price
        break
    elif num_drinks == m:
        break

print(sum_prices)
### BUGGY CODE ###

N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

l = [[] for _ in range(N + 1)]

for py in PY:
    l[py[0]].append(py[1])

for py in PY:
    l[py[0]].sort()

for py in PY:
    print('{:0>6}'.format(py[0]) + '{:0>6}'.format(l[py[0]].index(py[1]) + 1))


### FIXED CODE ###

N, M = map(int, input().split())
PY = []
for i in range(M):
    p, y = map(int, input().split())
    PY.append([p, y, i])

PY.sort()

n = 1
now = PY[0][0]
for py in PY:
    if now != py[0]:
        now = py[0]
        n = 1
    py[1] = n
    n += 1

PY.sort(key=lambda val: val[2])

for py in PY:
    print('{:0>6}'.format(py[0]) + '{:0>6}'.format(py[1]))
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ll=[0]*(l[-1]+1)

for i in l:
    ll[i]+=1
for i in range(1,len(ll)):
    ll[i]+=ll[i-1]

ans=0
import itertools
for i,j in itertools.combinations(l,2):
    if max(i-j,j-i)<i+j-1:
        ans+=ll[min(len(ll)-1,i+j-1)]-ll[min(len(ll)-1,max(i-j,j-i))]
        if max(i-j,j-i)<i<i+j:
            ans-=1
        if max(i-j,j-i)<j<i+j:
            ans-=1
print(ans//3)

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.sort()
ll=[0]*(l[-1]+1)

for i in l:
    ll[i]+=1
for i in range(1,len(ll)):
    ll[i]+=ll[i-1]

ans=0
import itertools
for i,j in itertools.combinations(l,2):
    if max(i-j,j-i)<i+j-1:
        ans+=ll[min(len(ll)-1,i+j-1)]-ll[min(len(ll)-1,max(i-j,j-i))]
        if max(i-j,j-i)<i<i+j:
            ans-=1
        if max(i-j,j-i)<j<i+j:
            ans-=1
print(ans//3)
### BUGGY CODE ###

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

# define combination
fact = [1, 1]
for i in range(2, N+1):
    fact.append(fact[-1]*i)
def comb(n, r):
    return fact[n] // (fact[n - r] * fact[r])

# process
nums = [0]*(N+1)
combs = [0]*(N+1)
for a in A:
    nums[a] += 1

for i, n in enumerate(nums):
    combs[i] = comb(n, 2)

sumall = sum(combs)

ans = []
for i, a in enumerate(A):
    ans.append(sumall - combs[a] + comb(nums[a]-1, 2))

# output
for a in ans:
    print(a)


### FIXED CODE ###

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

# define combination
combs = [0, 0]
for i in range(2, N+1):
    combs.append(i*(i-1)//2)

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = [sumall]*N
for i, a in enumerate(A):
    n = nums[a]
    ans[i] += combs[n-1] - combs[n]

# output
for a in ans:
    print(a)
### BUGGY CODE ###

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

nmax = 0

for na in range(N-1, -2, -1):
    for nb in range(M-1, -2, -1):
        n = na + nb + 2
        if n < nmax:
            continue
        time = sum([A[i] for i in range(na+1)]) + \
            sum([B[i] for i in range(nb+1)])
        if time <= K:
            nmax = n

print(nmax)
exit()


### FIXED CODE ###

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

nmax = 0

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans = 0
j = M
for i in range(N + 1):
    if a[i] > K:
        break

    while b[j] + a[i] > K:
        j -= 1
    ans = max(ans, i+j)

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

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

dprint = lambda *x:x

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
__N = 4000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, __N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



def kumiawase(p, q):
    dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    kumi_include_half = kumi+int(n%2==0)
    for p in range(kumi+1):
        dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])


### FIXED CODE ###

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

dprint = lambda *x:x

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
__N = 8000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, __N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



def kumiawase(p, q):
    # dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    for p in range(kumi+1):
        # dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        # dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    # dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])
### BUGGY CODE ###

n,k=map(int,input().split())
if k==1 or n%k==0:
    ans=0
else:
    tp=-1
    while 1:
        x=abs(n-k)
        if tp==x:
            break
        tp=x
        y=abs(x-k)
        n=min(n,min(x,y))
    ans=min(n,min(x,y))
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
if k==1 or n%k==0:
    ans=0
else:
    if n/2<k:
        x=abs(n-k)
        y=abs(x-k)
        ans=min(n,min(x,y))
    else:
        x=n%k
        y=abs(x-k)
        ans=min(x,y)
print(ans)
### BUGGY CODE ###

import math

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 += math.gcd(c, math.gcd(a, b))
print(sum)


### FIXED CODE ###

from math import gcd

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(c, gcd(a, b))
print(sum)
### BUGGY CODE ###

from operator import itemgetter


def get_root(A):
    res = [A]
    search = [A]

    while(len(search) > 0):
        now = search.pop()
        for a in ans[now-1]:
            if a == 0:
                continue
            res.append(a)
            search.append(a)
    return set(res)


N, M = map(int, input().split(" "))
AB = [list(map(int, input().split(" "))) for i in range(N+M-1)]

AB = sorted(AB, key=itemgetter(1))
count = 1
before = -1
temp = [AB[0][0]]
ans = [[0, ] for i in range(N)]
before = AB[0][1]
for a, b in AB[1:]:
    if before != b:
        ans[before-1] = temp
        temp = [a, ]
        before = b
    else:
        temp.append(a)

if len(temp) > 0:
    ans[-1] = (temp)
new_ans = []
for i, each_ans in enumerate(ans):

    if len(each_ans) == 1:
        new_ans.append(each_ans[0])
        continue
    for a in each_ans:
        if set(each_ans) & get_root(a) == set(each_ans):
            new_ans.append(a)
            break

for line in new_ans:
    print(line)


### FIXED CODE ###

from collections import deque
from operator import itemgetter


def topolo():
    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    res = []
    popleft, append = q.popleft, q.append
    res_append = res.append
    while q:
        v1 = popleft()
        res_append(v1)
        for v2 in edges[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                append(v2)
    return res


N, M = map(int, input().split(" "))
edges = [[] for _ in [0]*N]
rev = [[] for _ in [0]*N]

ins = [0]*N

for a, b in (map(int, input().split(" ")) for _ in [0]*(N+M-1)):
    edges[a-1].append(b-1)
    rev[b-1].append(a-1)
    ins[b-1] += 1

sorted_nodes = topolo()
order = [i for i, v in sorted(enumerate(sorted_nodes), key=itemgetter(1))]

for input_nodes in rev:
    l = len(input_nodes)
    if l == 0:
        print(0)
        continue
    elif l == 1:
        print(input_nodes[0] + 1)
        continue
    temp = 0
    for node in input_nodes:
        temp = max(temp, order[node])
    print(sorted_nodes[temp] + 1)
### BUGGY CODE ###

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

trans=[[] for _ in range(Q)]
for i in range(Q):
    B,C=map(int,input().split())
    trans[i].append(B)
    trans[i].append(C)

S=sum(A)
#まずはじめの合計求める

num=[0]*(10**5+1)
#これに数の出現回数をプロットする
for i in range(1,10**5+1):
    cnt=A.count(i)
    num[i]=cnt

for i in range(Q):
    B=trans[i][0]
    C=trans[i][1]
    change=num[B]*(C-B)
    num[C]+=num[B]
    num[B]-=num[B]
    S+=change
    print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = []
for i in range(Q):
    BC.append(list(map(int,input().split())))

num = [0]*(10**5+1)

S = []
 
#1 iterlation
S.append(sum(A))
for i in range(N):
    num[A[i]]+=1

    
for j in range(Q):
    if num[BC[j][0]] != 0:
        #Bに当たる交換するものがある時
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1] + (C - B)*num[B] )
        #S[-1]で合計の一番最新のもの
        dammy = num[B]
        num[B] = 0
        num[C] += dammy
 
    else:
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1])

        
for i in range(1,Q+1):
    print(S[i])