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

N = int(input())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
 
sum_xor = 0
for a in a_list:
    for b in b_list:
        sum_xor ^= a + b
 
print(sum_xor)    

### FIXED CODE ###

import sys
sdin = sys.stdin.readline


# 入力
n = int(sdin())
a = list(map(int, sdin().split()))
b = list(map(int, sdin().split()))

ans = 0

# バケットソートする
for k in range(29):
    a_nex = [[],[]]
    b_nex = [[],[]]
    for ai in a:
        a_nex[(ai & (1<<k)) >> k].append(ai)
            
    for bj in b:
        b_nex[(bj & (1<<k)) >> k].append(bj)
    

    a = []
    b = []
    for i in range(2):
        a = a + a_nex[i]
        b = b + b_nex[i]
        
    mask = pow(2,k+1) - 1
    a_mask = [ai & mask for ai in a]
    b_mask = [bj & mask for bj in b]
    
    base = pow(2,k)
    itr = [n]*4
    count = 0
    for ai in a_mask:
        border = [
                base - ai,
                2*base - ai,
                3*base - ai,
                4*base - ai
        ]
        
        for i in range(4):
            while 0 < itr[i] and border[i] <= b_mask[itr[i] - 1]:
                itr[i] -= 1
            
            
        count += ((itr[1] - itr[0]) + (itr[3]) - itr[2])
    
    if count & 1:
        ans += base
    
    
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    for i in range(10**10000):
        sp = s.split('ST', 1)
        if len(sp) > 1:
            s = sp[0] + sp[1]
        else:
            break
    print(len(s))

if __name__ == '__main__':
    main()

### FIXED CODE ###

s = input()
cnt = 0
while cnt < 100000:
    n = len(s)
    s = ''.join(s.split('ST'))
    if len(s) != n:
        cnt += (len(s) - n) // 2
    else:
        break
    i = s.find('ST')
    
    stlen = 0
    if i > 0:
        for j in range(min(i, len(s)-2-i)):
            if s[i-j-1] == 'S' and s[i+j+2] == 'T':
                stlen += 1
            else:
                break
        s = s[:i-stlen] + s[i+stlen+2:]
        cnt += 1 + stlen
print(len(s))
### BUGGY CODE ###

N = int(input())
S = str(input())
ans = 0

for j in range(1, N+1):
    if S[-j] == '#':
        j += 1
    else:
        break

if j == 1:
    last = 0
else:
    last = j-1
i = 0
while i < N:
    if S[i:i+2] == '#.':
        ans += 1
        S = S[:i+1] + '#' + S[i+2:]
    i += 1

print(min(ans, N-ans-last))

### FIXED CODE ###

N = int(input())
S = str(input())

ans = [S.count('.')]
for i in range(N):
    temp = ans[-1]
    if S[i] == '#':
        temp += 1
    else:
        temp -= 1
    ans.append(temp)
    
print(min(ans))
### BUGGY CODE ###

# 参考: https://cinnamo-coder.hatenablog.com/entry/2019/05/11/191130


n, k = map(int, input().split())
lst_h = list(map(int, input().split()))


# 1. DP[i] は、足場 i に到達するための最小コストと定義する
# 2. 状態遷移は min を使う
# 3. DPの初期化は、最小値を求めるので INF とする（足場1は例外）。
dp = [float("INF")] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        # n 番目の足場を跳び越したら、次の足場を調べる
        if i + j > n - 1:
            break
        # 既存の dp[i + j] と、新たに計算する dp[i + j] の大小比較
        dp[i + j] = min(dp[i + j], dp[i] + abs(lst_h[i] - lst_h[i + j]))


# 計算量 O(nk)
ans = dp[n - 1]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
lst_h = list(map(int, input().split()))


dp = [float("INF")] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j > n - 1:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(lst_h[i] - lst_h[i + j]))


ans = dp[n - 1]
print(ans)
### BUGGY CODE ###

MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

dp={i:0 for i in range(13)}
dp[0]=1

for i in range(n):
    next_dp={i:0 for i in range(13)}
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            next_dp[(j*10+k)%13] += dp[j]
    dp = {i:next_dp[i]%MOD for i in range(13)}

print(dp[5])

### FIXED CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)
### BUGGY CODE ###


n,m=map(int,input().split())
zahyo=[0]*m
for i in range(m):
    zahyo[i]=list(map(int,input().split()))

collec_lis=[]
for i in range(m):
    collec_lis.extend(list(range(int(zahyo[i][0]),int(zahyo[i][1])+1)))
    
import collections
c = collections.Counter(collec_lis)

kyotu=[int(i) for i in list(c.values()) if i==m]
print(len(kyotu))

### FIXED CODE ###


# 左右の範囲を絞っていくことで共通要素のみを炙り出す
n,m = map(int,input().split())
l = -1
r = n+1
for i in range(m):
    l_i,r_i = map(int,input().split())
    l = max(l,l_i)
    r = min(r,r_i)
print(max(0,r-l+1))
### BUGGY CODE ###

x = int(input())
import math
from collections import defaultdict
def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1
if isprime(x):
    print(1)
else:
    res = 0
    value = defaultdict(int)
    def bprime(n):
        cnt = 2
        while n != 1:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
    def cal(n):
        j  = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)

### FIXED CODE ###

x = int(input())
import math
from collections import defaultdict

res = 0
value = defaultdict(int)
def isprime(n):
    if n <= 1:
        return 0
    m = int(math.sqrt(n)) + 1
    for i in range(2, m):
        if n % i == 0:
            return 0
    return 1
if isprime(x):
    print(1)
else:
    def bprime(n):
        cnt = 2
        m = int(math.sqrt(n)) + 1
        while n != 1 and cnt < m:
            while n % cnt == 0:
                n //= cnt
                value[cnt] += 1
            cnt += 1
        if cnt == m and n != 1:
            value[n] += 1
    def cal(n):
        if n <= 2:
            return 1
        j = 1
        cnt = 0
        while n >= j:
            n -= j
            j += 1
            cnt += 1
        return cnt
    bprime(x)
    for key in value.keys():
        res += cal(value[key])
    print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

d = dict()
key_all = []
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    if a not in key_all:
        d[a] = [b]
        key_all.append(a)
    else:
        d[a].append(b)

key_all.sort()

ans = 0
l = []
import bisect

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                bisect.insort(l, v)

            key_all.pop(0)

    # print(l)

    if l != []:
        ans += l[-1]
        l.pop()
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

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

from collections import defaultdict


class Solution:
    def main(self):
        N, M = map(int, input().split())
        L = []
        R = []
        cards = set(list(range(1, N+1)))
        for _ in range(M):
            l, r = map(int, input().split())
            cands = set(list(range(l, r+1)))
            cards = cards & cands
        print(len(cards))


if __name__ == '__main__':
    Solution().main()

### FIXED CODE ###

from collections import defaultdict


class Solution:
    def main(self):
        N, M = map(int, input().split())
        L = []
        R = []
        cards = set(list(range(1, N+1)))
        left = 1
        right = N
        for _ in range(M):
            l, r = map(int, input().split())
            if right < l or r < left:
                print(0)
                return 0

            left = max(l, left)
            right = min(r, right)
        else:
            print(right-left+1)
            return


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

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

ans_max = M//N
ans = 0

for i in range(N,M+1):
    if M % i == 0:
        ans = int(M/i)
        break

print(ans)

### FIXED CODE ###

N,M = list(map(int, input().split()))
divi = []

for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        if i >= N:
            divi.append(i)
        if i != M//i:
            if M//i >= N:
                divi.append(M//i)

print(M//min(divi))
### BUGGY CODE ###

n = int(input())
a = 10**9 + 7
pow = 1
for i in range(n):
    pow *= i+1
print(pow % a)


### FIXED CODE ###

import math
n = int(input())
print(math.factorial(n)%(10**9+7))
### BUGGY CODE ###

N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*N
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in range(N-1):
    print(distance[i])

### FIXED CODE ###

N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*N
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in range(N-1):
    print(distance[i])
### BUGGY CODE ###

import math
import copy
from queue import Queue

n = int(input())
#n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#num = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
#s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

queue = Queue()
temp = 0

if (n < 10):
    print(n)
else:
    for i in range(1,10):
        queue.put(i)
    for i in range(1,n):
        temp = queue.get()
        if (temp % 10 != 0) :
            queue.put(10 * temp + (temp % 10) - 1)
        queue.put(10 * temp + (temp % 10))
        if (temp % 10 != 9) :
            queue.put(10 * temp + (temp % 10) + 1)

print(queue.get())



### FIXED CODE ###

import math
import copy
from queue import Queue

n = int(input())
#n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#num = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
#s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

queue = Queue()
temp = 0

if (n < 10):
    print(n)
else:
    for i in range(1,10):
        queue.put(i)
    for i in range(1,n):
        temp = queue.get()
        if (temp % 10 != 0) :
            queue.put(10 * temp + (temp % 10) - 1)
        queue.put(10 * temp + (temp % 10))
        if (temp % 10 != 9) :
            queue.put(10 * temp + (temp % 10) + 1)
    print(queue.get())
### BUGGY CODE ###

N = int(input())

def count(a, b, c):
    return (a+b+c)**2-a*b-b*c-c*a

for i in range(1, N+1):
    ans = 0
    for x in range(1, 41):
        for y in range(1, 41):
            for z in range(1, 41):
                tmp = count(x, y, z)
                if tmp > N:
                    break
                if tmp == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())

def count(a, b, c):
    return (a+b+c)**2-a*b-b*c-c*a

table = [0] * (N+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp = count(x, y, z)
            if tmp <= N:
                table[tmp] += 1
print(*table[1:], sep="\n")
### BUGGY CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapでソートを保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

q.sort()

min_se = 10**18
flag = False # min_seが正しい

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)
max_f = 0
for d in range(1,len(bit))[::-1]:
   #d-bit目まではKと同じ
   #XがKより大きくならないように、上位ビットをKに合わせる。
    d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    for e in range(2,len(bit))[::-1]:
        e=e-2
        mask = 1<<e
        num=0
        for a in A:#e-bit目が立っているA[i]を数える
            if a&mask:
                num+=1
        n_num = N - num
        #A[i]のe-bit目が立っていれば、XORの計算上0になるので、e-bit目が立っていないA[i]が加算
        if e>d:#dビット目より上はKに合わせる
            #以下、e-bit目だけ計算したf(x)
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:#どうせ後から計算するからなんでもよい？
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0
#for d in range(1,len(bit))[::-1]:
for d in range(41,-2,-1):
    #d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    #for e in range(2,len(bit))[::-1]:
    for e in range(41,-1,-1):
        #e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)
### BUGGY CODE ###

if __name__ == "__main__":
    from collections import deque
    N = int(input())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        edges[a].append((b,i))
        edges[b].append((a,i))

    color = [None]*(N-1)
    SIZE = 1
    q = deque([(0,None)])
    while q:
        v, prev_color = q.popleft()
        colors = list(range(1,SIZE+1))
        if prev_color:
            colors.remove(prev_color)
        for w, i in edges[v]:
            if not color[i]:
                if colors:
                    color[i] = colors.pop(0)
                else:
                    SIZE += 1
                    color[i] = SIZE
                q.append((w,color[i]))
    print(SIZE)
    for n in range(N-1):
        print(color[n])

### FIXED CODE ###

if __name__ == "__main__":
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        edges[a].append((b,i))
        edges[b].append((a,i))

    color = [None]*(N-1)
    SIZE = 1
    q = deque([(0,None)])
    while q:
        v, prev_color = q.popleft()
        c = 1
        for w, i in edges[v]:
            if not color[i]:
                if c == prev_color:
                    c += 1
                color[i] = c
                c += 1
                q.append((w,color[i]))
        SIZE = max(SIZE, c-1)
    print(SIZE)
    for n in range(N-1):
        print(color[n])
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()

for _ in range(Q):
  l, r = map(int, input().split())
  x = s[l - 1:r]
  ans = 0
  for i in range(len(x) - 1):
    if x[i:i + 2] == 'AC':
      ans += 1
  print(ans)


### FIXED CODE ###

from itertools import accumulate
from operator import add

N, Q = map(int, input().split())
S = input()
idx_list = [1 if S[i:i + 2] == 'AC' else 0 for i in range(len(S) - 1)]
idx_list_cumsum = [0] + list(accumulate(idx_list, add))

for _ in range(Q):
  l, r = map(int, input().split())
  print(idx_list_cumsum[r - 1] - idx_list_cumsum[l - 1])
### BUGGY CODE ###

N,K=[int(s) for s in input().split(" ")]
ListH=[int(s) for s in input().split(" ")]

#ListH.sort(reverse=True)
sum=0

if N > K:
    for i in range(K):
        ListH.remove(max(ListH))
        
    for i in range(N-K):
        sum+=ListH[i]
else:
    sum=0
    
print(sum)

### FIXED CODE ###

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


if N<=K:
    print(0)
else:
    ListH.sort()
    sum=0
    for i in range(N-K):
        sum+=ListH[i]

    print(sum)
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
S = []
As2 = As + As
for i in range(N):
  a = As[i]
  for j in range(i+1, 2*N):
    if As2[j] == a:
      S.append(j)
      break
#print(S)
count = 0
p = 0
while True:
  n = S[p]+1
  count += n // N
  p = n % N
  if p == 0:
    break
#print(count)
if count < 0:
  print(" ".join(map(str, s)))
else:
  K = K%count
  s = []
  for k in range(K):
    for a in As:
      i = -1
      for j in range(len(s)):
        if s[j] == a:
          i = j
      if i < 0:
        s.append(a)
      else:
        s = s[0:i]
  print(" ".join(map(str, s)))


### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
s = []
while p < N*K:
  q = p+S[p%N]
  if q > N*K:
    s.append(As[p%N])
    p = p+1
  else:
    p = q
print(" ".join(map(str, s)))
### BUGGY CODE ###

class BinaryIndexedTree:  # 0-index !!!
    """
    init(n):     要素数nを与えて0で初期化
    add(i, x):   i番目の値にxを追加 O(logN)
    sum(i):      区間[0,i)の和を返す O(logN)
    query(l, r): 区間[l,r)の和を返す O(logN)
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def set(self, i, x):
        now = self.query(i, i + 1)
        self.add(i, -now + x)

    def sum(self, i):  # 0-index  sum of [0,i)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        tmp = t1[x]
        ans -= tmp - 2
        if x < w:
            w = x
            for i in range(h + 1):
                t2[i] = w
    else:
        tmp = t2[x]
        ans -= tmp - 2
        if x < h:
            h = x
            for i in range(w + 1):
                t1[i] = h
print(ans)


### FIXED CODE ###

n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        if x < w:
            tmp = h
            for i in range(x, w+1):
                t1[i] = h
            w = x
        else:
            tmp = t1[x]
        ans -= tmp - 2
    else:
        if x < h:
            tmp = w
            for i in range(x, h+1):
                t2[i] = w
            h = x
        else:
            tmp = t2[x]
        ans -= tmp - 2
print(ans)
### BUGGY CODE ###

def modinv2(a,m):
    return pow(a,m-2,m)

def f(n,m):
    a = 1
    for i in range(2,n+1):
        a = a*i%m
    return a

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

ans = 0
P = 10**9+7

b = f(N-1,P)

for i in range(N-1):
    l = x[i+1]-x[i]
    for j in range(i+1):
        c = modinv2(j+1,P)
        ans += (l*c%P)*b%P

print(ans%P)


### FIXED CODE ###

def modinv2(a,m):
    return pow(a,m-2,m)

def f(n,m):
    a = 1
    for i in range(2,n+1):
        a = a*i%m
    return a

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

ans = 0
P = 10**9+7

b = f(N-1,P)

invlist = [1]

for i in range(1,N-1):
    inv = (invlist[-1]+modinv2(i+1,P))%P
    invlist.append(inv)
#print(invlist)

for i in range(N-1):
    l = x[i+1]-x[i]
    ans += (l*invlist[i]%P)*b%P

print(ans%P)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
A = Counter(A)
bc = [tuple(map(int, input().split())) for i in range(Q)]

ans = 0
for b, c in bc:
    v = A.pop(b, None)
    if v:
        A[c] += v
    ans = 0
    ans = sum(i*j for i, j in A.items())
    print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
A = Counter(A)
bc = [tuple(map(int, input().split())) for i in range(Q)]
for b, c in bc:
    v = A.pop(b, None)
    if v:
        A[c] += v
        ans = ans+((c-b)*v)
    print(ans)