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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
for _ in range(Q):
    ans = 0
    l, r = na()
    t = (r - l) // D
    for j in range(t):
        px, py = d[l + j * D]
        nx, ny = d[l + (j + 1) * D]
        #print(px, py, nx, ny)
        ans += abs(px - nx) + abs(py - ny)
    print(ans)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

dp = [0 for _ in range(H*W+1)]

for i in range(1, D+1):
    dp[i] = 0

for i in range(D+1, H*W+1):
    ni, nj = d[i]
    pi, pj = d[i - D]
    dp[i] = dp[i - D] + abs(ni - pi) + abs(nj - pj)

for i in range(Q):
    ans = 0
    l, r = na()
    ans = dp[r] - dp[l]
    print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = []
for i in range(q):
    a.append(int(input()))
# n, k, q = 6, 3, 4
# a = [3, 1, 3, 2]
ans = []
s = []
for i in range(n):
    ans.append('Yes')
    s.append(k)
# print(s, ans)
for i in range(q):
    s[a[i] - 1] += 1
    for j in range(n):
        s[j] -= 1
        if s[j] <= 0:
            ans[j] = 'No'
print('\n'.join(ans))


### FIXED CODE ###

n, k, q = map(int, input().split())
a = []
for i in range(q):
    a.append(int(input()))
# n, k, q = 6, 3, 4
# a = [3, 1, 3, 2]
ans = []
s = []
for i in range(n):
    # ans.append('Yes')
    s.append(k - q)
# print(s, ans)
for i in range(q):
    s[a[i] - 1] += 1
ans = []
for i in s:
    if i > 0:
        ans.append('Yes')
    else:
        ans.append('No')
# print(s)
print('\n'.join(ans))
### BUGGY CODE ###

N=int(input())
word=[]
for i in range(N):
  word.append(input())
  
alphalist=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
numlist=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]


numberlist=[]
for i in range(N):
  wordnum0=1
  word0=word[i]
  for v in range(10):
    for k in range(26):
      if word0[v]==alphalist[k] :
        wordnum0*=numlist[k]
        break
  numberlist.append(wordnum0)

number=0
for i in range(N):
  freq=numberlist.count(numberlist[i])
  if freq!=1:
    number0=(freq*(freq-1))/2
    number0=number0/freq
    number+=number0
  
print(int(number))

### FIXED CODE ###

n = int(input())
s = [input()for _ in range(n)]

for i in range(n):
    s[i] = ''.join(sorted(s[i]))

s.sort()

ans = 0
count = 0

for i in range(1, n):
    if count == 0:
        if s[i] == s[i-1]:
            count = 2
    else:
        if s[i] == s[i-1]:
            count += 1
        else:
            ans += count * (count - 1) // 2
            count = 0

ans += count * (count - 1) // 2

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

k,s = list(map(int,input().split()))

def fact(n):
  return sum([x for x in range(1,n+1)])

ans = 0
r = 0
for x in range(k+1):
  for y in range(x,k+1):
    for z in range(y,k+1):
      if x+y+z == s:
        if x == y == z:
          ans += 1
        elif (x==y) or (x==z) or (y==z):
          ans += fact(2)
        else:
          ans += fact(3)

print(ans)


### FIXED CODE ###

k,s = list(map(int,input().split()))

def fact(n):
  return sum([x for x in range(1,n+1)])

ans = 0
r = 0
for x in range(k+1):
  for y in range(x,k+1):
    if 0 <= s - (x+y) <= k:
      if (x==y):
          ans += 1
      else:
          ans += 2

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

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

from fractions import gcd

def lcm(x, y):
    g = gcd(x, y)
    return x * y // g

l = 1
for e in a:
    l = lcm(l, e)

ans = 0
for e in a:
    add = l // e
    ans += add
    ans %= mod

print(ans)


### FIXED CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

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

N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()

damege_sum = 0
ans = 0
q = []
for i in range(N):
    x, h = monsters[i]
    while q:
        if q[0][0] < x:
            damege_sum -= q[0][1]
            q.pop(0)
    h -= damege_sum
    if h > 0:
        hit = -(-h // A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)




### FIXED CODE ###

from math import ceil


N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()


def problem_a(h):
    if h <= 0:
        return 0
    return ceil(h/A)


cnt_sum = 0
cnt = [0] * N
l = 0
for i in range(N):
    while monsters[l][0] + 2 * D < monsters[i][0]:
        cnt_sum -= cnt[l]
        l += 1
    already = cnt_sum * A
    cnt[i] = problem_a(monsters[i][1] - already)
    cnt_sum += cnt[i]

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

H,W=map(int,input().split())

A=[list('X'+input()+'X') for i in range(H)]
A.append('X'*(W+2))
A.insert(0,'X'*(W+2))
d=[[0,1],[0,-1],[1,0],[-1,0]]
wnum=0
blis=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=='.':
            wnum+=1
        if A[i][j]=='#':
            blis.append([i,j])

if wnum==0:
    print(0)
    exit()

ans=0
wtob=0
while len(blis):
    ans+=1
    nblis=[]
    for p in blis:
        for v in d:
            ny=p[0]+v[0]
            nx=p[1]+v[1]
            if A[ny][nx]=='.':
                A[ny][nx]='#'
                nblis.append([ny,nx])
                wtob+=1
    if wtob==wnum:
        print(ans)
        exit()
    blis=[]
    for i in nblis:
        blis.append(i)


### FIXED CODE ###

H,W=map(int,input().split())

A=[list('X'+input()+'X') for i in range(H)]
A.append('X'*(W+2))
A.insert(0,'X'*(W+2))
d=[[0,1],[0,-1],[1,0],[-1,0]]
wnum=0
blis=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=='.':
            wnum+=1
        if A[i][j]=='#':
            blis.append([i,j])

if wnum==0:
    print(0)
    exit()

ans=0
wtob=0
while len(blis):
    ans+=1
    nblis=[]
    for p in blis:
        for v in d:
            ny=p[0]+v[0]
            nx=p[1]+v[1]
            if A[ny][nx]=='.':
                A[ny][nx]='#'
                nblis.append([ny,nx])
                wtob+=1
    if wtob==wnum:
        print(ans)
        exit()
    blis=[]
    for i in nblis:
        blis.append(i)
### BUGGY CODE ###

import re
s = input()
s = s[::-1]

for i in range(len(s)//5):
    s = re.sub("^remaerd", "", s)
    s = re.sub("^maerd", "", s)
    s = re.sub("^resare", "", s)
    s = re.sub("^esare", "", s)

if s == "":
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = input()

while True:
    for word in ["dream", "dreamer", "erase", "eraser"]:
        if s.endswith(word):
            s = s[:-len(word)]
            break
    else:
        print("NO")
        exit()
    if s == "":
        print("YES")
        break
### BUGGY CODE ###

N = input()
A = list(map(int,input().split()))
ans = A[0]
for i in range(1,len(A)):
  ans = ans * A[i]
ans2 = ans

if ans2 - 10 ** 18 <= 0:
  print(ans)
else:
  print('-1')

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
    print(0)
    return
  
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
  
main ()
### BUGGY CODE ###

import sys
n = int(input())
def DFS(n, t):
    tmp = 10**5
    if t<=5:
        for i in range(9):
            nxt = n-i*(9**(6-t))
            if nxt<0:
                continue
            tmp = min(tmp, DFS(nxt, t+1)+i)
        return tmp
    elif t<=11:
        for i in range(6):
            nxt = n-i*(6**(12-t))
            if nxt<0:
                continue
            tmp = min(tmp, DFS(nxt, t+1)+i)
        return tmp
    else:
        if n<6:
            return n
        else:
            return 10**5
print(DFS(n, 1))

### FIXED CODE ###

import sys
n = int(input())
INF = 10*n
dp = [INF]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    tmp = dp[i-1] + 1
    for j in range(10):
        if i-6**j<0:
            break
        tmp = min(tmp, dp[i-6**j] + 1)
    for j in range(10):
        if i-9**j<0:
            break
        tmp = min(tmp, dp[i-9**j] + 1)
    dp[i] = tmp
print(dp[n])
### BUGGY CODE ###

#!/usr/bin/env python3

S = input()
lis_2019 = [2019 * i for i in range(1, 99)]
cnt = 0
S_len = len(S)
cnt_1 = 0
S_lis = [S]

for i in range(4, S_len):
    while cnt_1 != S_len - i + 1:
        #print(S[cnt_1:cnt_1+1+i])
        S_lis.append(S[cnt_1:cnt_1+i])
        cnt_1 += 1
    cnt_1 = 0

for i in S_lis:
    for j in lis_2019:
        if str(i) == str(j):
            cnt += 1

print(cnt)

### FIXED CODE ###

#!/usr/bin/env python3

S = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for i in S:
    num += int(i) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for i in counts:
    ans += i * (i - 1) // 2

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

N = int(input())
a = [int(input()) for i in range(N)]

counter = 0
for i in set(a):
	if a.count(i)%2 == 1:
		counter += 1
print(counter)


### FIXED CODE ###

#ソートして左から数えるver
N = int(input())
a = sorted([int(input()) for i in range(N)])

count_list = [1]*len(set(a))
j = 0

for i in range(len(a)-1):
	if a[i] == a[i+1]:
		count_list[j] += 1
	else:
		j += 1

print(sum([ i%2 == 1  for i in count_list]))
### BUGGY CODE ###

import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
S = [0] * N
S[0] = 0
 
for i in range(1, N):
    value = math.inf
    maxStep = min(K, i)
    for step in range(1, maxStep + 1):
        value = min(value, S[i - step] + abs(h[i] - h[i - step]))
    S[i] = value
print(S[N - 1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-K),i))
print(dp[N-1])
### BUGGY CODE ###

import re


n, q = [int(i) for i in input().split()]
s = input()
for i in range(q):
    l, r = [int(i) for i in input().split()]
    l -= 1
    substr = s[l:r]
    print(len(re.findall(r"AC", substr)))


### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()

count = [0] * (n + 1)
for i in range(n):
    count[i+1] += count[i]
    if s[i:i+2] == "AC":
        count[i+1] += 1
for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


    for i in range(1,b + 1):
        P_ni*=(n-i+1)%MOD
        F_i*= i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)



    print(s%MOD)

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


    for i in range(1,b + 1):
        P_ni=P_ni*(n-i+1)%MOD
        F_i=F_i* i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)



    print(s%MOD)

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

import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
N, W = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]
# sum_vの取りうる上限値
MAX_V = (10**3 + 1) * N
# 最小値を求めるので無限大の値
f_inf = float('inf')


def chmin(a, b):
    if a <= b:
        return a
    else:
        return b


def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf] * MAX_V for j in range(N + 1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        # w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if sum_v - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    # dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)


knapsack(N, W)


### FIXED CODE ###

import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
N, W = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]
# sum_vの取りうる上限値
# MAX_V = (10**3 + 1) * N
MAX_V = 0
for line in array:
    MAX_V += line[1]
MAX_V += 1
# 最小値を求めるので無限大の値
f_inf = float('inf')


def chmin(a, b):
    if a <= b:
        return a
    else:
        return b


def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf] * MAX_V for j in range(N + 1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        # w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if sum_v - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    # dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)


knapsack(N, W)
### BUGGY CODE ###

N = int(input())
x = list(map(int, input().split()))
def div(i):
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i <<= 1
    return cnt

print(min(list(map(div, x))))

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
mn_lst = []
for i in x:
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i >>= 1
    mn_lst.append(cnt)
    
print(min(mn_lst))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in a:
    #print(i)
    b.append(i)
    b = b[::-1]
    #print(b)
print(*b)

### FIXED CODE ###

from collections import deque

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

for i in range(len(a)):
    if (n-i)%2 == 1:
        b_deque.appendleft(a[i])
    else:
        b_deque.append(a[i])
print(*b_deque)
### BUGGY CODE ###

import math
from collections import Counter

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n = int(input())
    array_s = []
    array = []
    for i in range(n):
        array_s.append(input())

    for s in array_s:
        array.append(Counter(s))

    ans = 0
    for i in range(n):
        if not array:
            break
        alphabet = array[:][0]
        num = array.count(alphabet)-1
        if num <= 0:
            pass
        elif num <= 1:
            ans += 1
        else:
            ans += combinations_count(num+1, 2)
        for j in range(num+1):
            array.remove(alphabet)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    array_s = []
    array = []
    for i in range(n):
        array_s.append(input())

    for s in array_s:
        array.append(''.join(sorted(s)))
    array = sorted(array)
    ans = 0
    count = 1
    for i in range(n-1):
        if array[i] == array[i+1]:
            count += 1
            if i != n-2:
                continue
        ans += int(count*(count-1)/2)
        count = 1
    print(ans)


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

N = int(input())
s = ['' for i in range(N)]
for i in range(N):
  s[i]=input()

lsts=list(set(s))
lsts.sort()
n = [0 for i in range(len(lsts))]
for i in range(len(lsts)):
  n[i]=s.count(lsts[i])
  
ind=[i for i in range(len(lsts)) if n[i]==max(n)]
for i in ind:
  print(lsts[i])

### FIXED CODE ###

N = int(input())
dc={}
for i in range(N):
  s=input()
  if s in dc:
    dc[s]+=1
  else:
    dc[s]=1
m=max(dc.values())
w = [kv[0] for kv in dc.items() if kv[1] == m]
w.sort()
for p in w:
  print(p)
### BUGGY CODE ###

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    unum=[]
    for i in range(p):
        unum.append(0)
    num=0
    for i in range(n):
        unum[int(s[i:n])%p]+=1
    unum[0]+=1
    for i in range(p):
        count+=(unum[i]*(unum[i]-1))*0.5
print(round(count))

### FIXED CODE ###

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    lis=[1]
    for i in range(n-1):
        lis.append((lis[i]*10)%p)
    lis.reverse()
    for i in range(n):
        lis[i]=(int(s[i])*lis[i])%p
    unum=[1]
    for i in range(p-1):
        unum.append(0)
    num=0
    for i in range(n):
        num=(num+lis[n-i-1])%p
        unum[num]+=1
    for i in range(p):
        unumi=unum[i]
        count+=(unumi*(unumi-1))*0.5
print(round(count))
### BUGGY CODE ###

import decimal


def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)


main()


### FIXED CODE ###

import decimal
 
 
def main():
    N, K = map(int, input().split())
    ans = 0
    for n in range(1, N + 1):
        s = 0
        s += n
        c = 0
        while K > s:
            s *= 2
            c += 1
        ans += decimal.Decimal((1 / N) * (1 / 2) ** c)
    print(ans)
 
 
main()
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        if ans == H + W - 1:
            break
        continue

    if is_okay(x+1,y): q.put([x+1,y,n])
    if is_okay(x-1,y): q.put([x-1,y,n])
    if is_okay(x,y+1): q.put([x,y+1,n])
    if is_okay(x,y-1): q.put([x,y-1,n])
    visited[y][x] = True

if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break

    if is_okay(x+1,y):
        q.put([x+1,y,n])
        visited[y][x+1] = True
    if is_okay(x-1,y):
        q.put([x-1,y,n])
        visited[y][x-1] = True
    if is_okay(x,y+1):
        q.put([x,y+1,n])
        visited[y+1][x] = True
    if is_okay(x,y-1):
        q.put([x,y-1,n])
        visited[y-1][x] = True


if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)
### BUGGY CODE ###


n = int(input())

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


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            return max(gcd_list(li[:j] + li[j + 1:]) for j in range(i))
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)

### FIXED CODE ###


n = int(input())

a = list(map(int, input().split()))
a.sort(reverse=True)


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            if i == n - 1:
                return gcd_list(li[:i])
            gg = gcd_list(li[i+1:])
            bb = [gcd(li[x], gg) for x in range(i+1)]
            bb.sort()
            return bb[1]
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
process = []
proc_append = process.append
for i in range(Q):
	proc_append(tuple(input().split()))
	process[i] = tuple(map(int,process[i]))

for b,c in process:
	A.sort()
	if b in set(A):
		for i in range(N):
			if b==A[i]:
				begin = i
				break
		for i in range(begin,N):
			if b!=A[i]:
				end = i-1
				break
			if i==N-1:
				end = i
		for i in range(begin,end+1):
			A[i] = c
	print(sum(A))

### FIXED CODE ###

# 整数の入力
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
process = []
proc_append = process.append
hash = [0]*100001
for i in range(Q):
    proc_append(tuple(input().split()))
    process[i] = tuple(map(int,process[i]))

goukei = sum(A)

for i in A:
	hash[i] += 1

for b,c in process:
	if hash[b] != 0:
		goukei += (c-b)*hash[b]
		hash[c] += hash[b]
		hash[b] = 0
	print(goukei)