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

T = int(input())
a = []
for i in range(T):
    a.append(list(map(int, input().split())))
for r in a:
    s, b, c, d = r[0], r[1], r[2], r[3]
    if (s < b) or (b>d):
        print('No')
        continue


    s_list = []
    while True:
        s_list.append(s)
        if s > b*2:
            s -= b*((s//b)-1)
            while s <= c:
                s+= c
        s -= b
        if s in s_list:
            print('Yes')
            break
        s_list.append(s)


        if s <0:
            print('No')
            break
        if s <= c:
            s += d
            s_list.append(s)
            if s != s_list[-1]:
                if s in s_list:
                    print('Yes')
                    break


### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


T = int(input())
a = []
for i in range(T):
    a.append(list(map(int, input().split())))
for r in a:
    s, b, c, d = r[0], r[1], r[2], r[3]
    mod_list = []
    if (s < b) or (b>d):
        print('No')
        continue
    if (c>b):
        print('Yes')
        continue

    g = gcd(b,d)

    if b- g + s%g > c:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())

A = []
for h in range(1, N+1):
    if N % h == 0:
        A.append([h , int(N/h)])

B = []
for k in range(len(A)):
    B.append(A[k][0] + A[k][1])
C = min(B)
print(C - 2)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())

tmp = 10 ** 24
tmp2 = 1
tmp3 = 1
for i in range(1, 10 ** 6 + 1):
    if n % i == 0 and i + (n / i) < tmp:
        tmp = i + (n // i)
        tmp2 = i
        tmp3 = n // i
print(tmp2 + tmp3 - 2)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
    
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

                
if d[dh-1][dw-1] == 10000000:
    print(-1)
else:
    print(d[dh-1][dw-1])
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.append((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# for i in temp:
#     print(i)
print(temp[gy+1][gx+1])

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.appendleft((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# for i in temp:
#     print(i)
print(temp[gy+1][gx+1])
### BUGGY CODE ###

from collections import Counter

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


a_min = float("inf")
a_max = 0
a_diff = 0

counter = Counter([])

for a in A:
    hasModefied = False
    if a_min > a:
        a_min = a
        a_max = a
    if a_max < a:
        a_max = a
        hasModefied = True
        
    if hasModefied:        
        a_diff = a_max - a_min
        counter += {a_diff: 1}

keys = list(counter.keys())
max_key = max(keys)
print(counter[max_key])

### FIXED CODE ###

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


a_min = float("inf")
a_max = 0
a_diff = 0

ans = 0
a_diff = -1

for a in A:

    hasModefied = False
    if a_min > a:
        a_min = a
        a_max = a
    if a_max < a:
        a_max = a
        hasModefied = True
        
    if hasModefied:
        if a_diff == a_max-a_min:
            ans += 1
        elif a_diff < a_max-a_min:
            a_diff = a_max - a_min
            ans = 1
            
print(ans)
### BUGGY CODE ###

n=int(input())
li = list(map(int,input().split()))
ans=[]
a=""
for i in range(1,n+1):
  ans.append(li.index(i)+1)
for c in ans:
  a+=str(c)+" "
  
print(a)

### FIXED CODE ###

n=int(input())
li = list(map(int,input().split()))
ans=[0]*n
a=""
for (i,x) in zip(range(0,n), li):
  ans[x-1]=i+1
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a =[int(i) for i in input().split()]
b =[int(i) for i in input().split()]

cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k

print(cnt if a == b else -1)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

n = int(input())
a = [0]*n
b = [0]*n
a =[int(xi) for xi in input().split()]
b =[int(yi) for yi in input().split()]

cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k

print(cnt if a == b else -1)
### BUGGY CODE ###

import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    s2 = set([i for i in range(l,r+1) if i in p])
    s3 = set([i for i in s2 if (i+1)//2 in p])
    print(len(s3))

### FIXED CODE ###

import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s
p2 = set([i for i in p if (i+1)//2 in p])
c = 0
x = [0]*100001
for i in range(1,num+1):
    if i in p2:
        c+=1
    x[i]=c

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    ans = x[r]-x[l-1]
    print(ans)
### BUGGY CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
d = [a[0]]

for i in range(1, n):
    d.append(a[i] - a[i-1])
    
d.append(k - a[-1])

most_min_path = 10000

for i in range(n):
    if i == 0:
        normal_ck = sum(d) - d[i] - d[-1]
        reverse_ck = sum(d) - d[i+1]
    elif i == n - 1:
        normal_ck = sum(d) - d[i]
        reverse_ck = sum(d) - d[i+1] - d[0]
    else:
        normal_ck = sum(d) - d[i]
        reverse_ck = sum(d) - d[i+1]
    if normal_ck > reverse_ck:
        min_ck = reverse_ck
    else:
        min_ck = normal_ck
    
    if most_min_path > min_ck:
        most_min_path = min_ck

print(most_min_path)

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print(k - l)
### BUGGY CODE ###

import sys
S = input()
N = len(S)
words = ['dream', 'dreamer', 'erase', 'eraser']
i = 0
while i != N:
    flag = 1
    for word in words:
        if S[::-1][i:i+len(word)] == word[::-1]:
            flag = 0
            i += len(word)
    if flag:
        print('NO')
        sys.exit()
print('YES')

### FIXED CODE ###

import sys
S = input()
S = S[::-1]
N = len(S)
words = ['maerd', 'remaerd', 'esare', 'resare']
i = 0
while i != N:
    flag = 1
    for word in words:
        if S[i:i+len(word)] == word:
            flag = 0
            i += len(word)
    if flag:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

import copy

n = int(input())
lst = [[0]*2 for i in range(n)]
for i in range(n):
    lst[i][0], lst[i][1] = map(int, input().split())

lst.sort(key=lambda x:(x[1]))
lst.sort(key=lambda x:(x[0]))

lst_copy = copy.deepcopy(lst)
saidai = 0
for i in range(n-1):
    for j in range(i+1, n):
        cnt = 0
        p = lst[j][0] - lst[i][0]
        q = lst[j][1] - lst[i][1]
        lst_copy = copy.deepcopy(lst)
        while lst_copy != []:
            lst_k = lst_copy.pop(0)
            xs, ys = lst_k[0], lst_k[1]
            length = len(lst_copy)
            delete_lst = []
            lst_copy_copy = copy.deepcopy(lst_copy)
            for l in range(length):
                xl, yl = lst_copy[l][0], lst_copy[l][1]
                if xl == xs + p and yl == ys + q:
                    xs = xs + p
                    ys = ys + q
                    cnt += 1
                    lst_copy_copy.remove([xl, yl])
            lst_copy = lst_copy_copy
        saidai = max(saidai, cnt)

print(n-saidai)

### FIXED CODE ###

import copy

n = int(input())
lst = [[0]*2 for i in range(n)]
for i in range(n):
    lst[i][0], lst[i][1] = map(int, input().split())

lst.sort(key=lambda x:(x[1]))
lst.sort(key=lambda x:(x[0]))

lst_copy = copy.deepcopy(lst)
saidai = 0
for i in range(n-1):
    for j in range(i+1, n):
        cnt = 0
        p = lst[j][0] - lst[i][0]
        q = lst[j][1] - lst[i][1]
        lst_copy = copy.deepcopy(lst)
        while lst_copy != []:
            xs, ys = lst_copy[0][0], lst_copy[0][1]
            lst_copy.pop(0)
            while [xs+p, ys+q] in lst_copy:
                cnt += 1
                xs, ys = xs+p, ys+q
                lst_copy.remove([xs, ys])
        saidai = max(saidai, cnt)

print(n-saidai)
### BUGGY CODE ###

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

prime = []
numL = [i for i in range(2, 1000001)]
while True:
	p = numL[0]
	if p >= 1000:
		prime += numL
		break
	prime.append(p)
	numL = [i for i in numL if i % p != 0]

ans = 1
for i in prime:
	c = 0
	while True:
		if P % i == 0:
			c += 1
			P = int(P // i)
		else:
			break
	if c >= N:
		ans = ans * (i ** int(c // N))

print(ans)

### FIXED CODE ###

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

prime = [2, 3, 5]
numL = [i for i in range(2, 1000001) if i % 2 != 0 and i % 3 != 0 and i % 5 != 0]
while True:
	p = numL[0]
	if p >= 1000:
		prime += numL
		break
	prime.append(p)
	numL = [i for i in numL if i % p != 0]

if N == 1:
	print(P)

else:
	ans = 1
	for i in prime:
		c = 0
		while True:
			if P % i == 0:
				c += 1
				P = int(P // i)
			else:
				break
		if c >= N:
			ans = ans * (i ** int(c // N))
	print(ans)
### BUGGY CODE ###

import heapq

n, a, b = map(int, input().split())
h = [-int(input()) for i in range(n)]

heapq.heapify(h)
count = 0
while True:
    count += 1
    ele = -heapq.heappop(h)
    ele -= (a - b)
    heapq.heappush(h, -ele)
    ele = -heapq.heappop(h)
    if ele <= b * count:
        print(count)
        break
    heapq.heappush(h, -ele)

### FIXED CODE ###

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
  now=n
  for j in range(i,n):
    now=min(now,a[j])
    ans+=now
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
dn={x:i for i,x in enumerate(p)}

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

st=SegTree([0]*n)
ans=0

for k in range(1,n+1):
    i=dn[k]
    # idx=iを含み、区間和が0になる最長の区間を調べる。
    l,r=0,i
    while r-l>1:
        x=(l+r)//2
        if st.query(x,i+1)>0:
            l,r=x,r
        else:
            l,r=l,x
    l0=l if st.query(l,i+1)==0 else r
    l,r=i,n-1
    while r-l>1:
        x=(l+r)//2
        if st.query(i,x+1)>0:
            l,r=l,x
        else:
            l,r=x,r
    r0=r if st.query(i,r+1)==0 else l
    ans+=k*(i-l0+1)*(r0-i+1)
    st.update(i,1)
print(ans)
### BUGGY CODE ###

def main():
  N = int(input())
  def count(n):
    ret = 0
    i = 1
    while i*i <= n:
      if n % i == 0:
        ret += 1
        if i != n // i:
          ret += 1
      i += 1
    return ret


  ans = 1
  if N==1:
    print(ans)
  else:
    for i in range(2,N+1):
      x = count(i)
      ans += x * i

    print(ans)
    
main()

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
  x = N//i
  ans += i * x * (x + 1) // 2
  
print(ans)
### BUGGY CODE ###

S = input()
cnt = 0
is_end = [False] * (len(S) + 1)
for i in range(len(S)):
    if is_end[i]:
        continue
    is_end[i] = True
    bingo = [i]
    for j in range(i+1, len(S)+1):
        if is_end[j]:
            continue
        if int(S[i:j]) % 2019 == 0:
            is_end[j] = True
            bingo.append(j)
    l = len(bingo)
    if l >= 2:
        cnt += int(l*(l-1)/2)
print(cnt)


### FIXED CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10
    p %= 2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))
### BUGGY CODE ###

import itertools
D, G = map(int, input().split())
P = [list(map(int, input().split())) for i in range(D)]
min_num = 10**8

judge_list = list(itertools.product([0, 1, 2], repeat=D)) #0:中途半端に解く 1:一問も解かない 2: 全部解く

for judge in judge_list:
    score = 0
    num = 0
    for i in range(1, len(judge) + 1):
        if score >= G:
            break
        
        if judge[-i] == 1:
            pass
        
        if judge[-i] == 2:
            score += P[-i][0] * (D - i + 1) * 100 + P[-i][1]
            num += P[-i][0]
            
        if judge[-i] == 0:
            for j in range(P[-i][0]):
                if score >= G:
                    break
                score += 100 * (D - i + 1)
                num += 1
                        
    if score >= G:
        min_num = min(num, min_num)

print(min_num)           

### FIXED CODE ###

import itertools
from collections import Counter
D, G = map(int, input().split())
P = [list(map(int, input().split())) for i in range(D)]
min_num = 10**8

judge_list = list(itertools.product([0, 1, 2], repeat=D)) #0:中途半端に解く 1:一問も解かない 2: 全部解く


for judge in judge_list:
    score = 0
    num = 0
    d = Counter() #インスタンスを生成
    d.update(judge)
    if (d[0] <= 1):
        for i in range(1, len(judge) + 1):
            if score >= G:
                break

            if judge[-i] == 1:
                pass

            if judge[-i] == 2:
                score += P[-i][0] * (D - i + 1) * 100 + P[-i][1]
                num += P[-i][0]

            if (judge[-i] == 0):
                for j in range(P[-i][0]):
                    if score >= G:
                        break
                    score += 100 * (D - i + 1)
                    num += 1
                        
        if score >= G:
            min_num = min(num, min_num)

print(min_num)
### BUGGY CODE ###

def func(S,N):
    dic = {}
    for i in range(N):
        if dic.get(S[i],False):
            dic[S[i]] = dic[S[i]] + str(i)
        else:
            dic[S[i]] = str(i)
    tmp = []
    for value in dic.values():
        tmp.append(int(value))
    tmp.sort()
    return tmp
S = input()
T = input()
N = len(S)
if func(S,N) == func(T,N):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
t = input()
dict_st = {}
dict_ts = {}
for x, y in zip(s, t):
    if x not in dict_st:
        dict_st[x] = y
    else:
        if dict_st[x] != y:
            print("No")
            break
    if y not in dict_ts:
        dict_ts[y] = x
    else:
        if dict_ts[y] != x:
            print("No")
            break
else:
    print("Yes")
### BUGGY CODE ###

from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] <= a:
                        continue
                    ti[j] = a
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


### FIXED CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
C = collections.Counter(A)
Q = int(input())
X = [[] for _ in range(Q)]
for i in range(Q):
    X[i] = list(map(int, input().split()))

for i in range(Q):
    b, c = X[i]
    for j in range(C[b]):
        A.remove(b)
        A.append(c)
    C = collections.Counter(A)
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sum(A)
count = [0 for _ in range(int(1e5)+1)]
for a in A:
    count[a] += 1    

Q = int(input())
for i in range(Q):
    b, c = map(int, input().split())
    S += (c-b) * count[b]
    count[c] += count[b]
    count[b] = 0
    print(S)