Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# input
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

# process
XH.sort()
#print(XH)

ans = 0
for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue

    XH[i][1] = 0
    c = -(-h//A)
    ans += c

    dmg = A*c
    scp_end = x+D*2

    for j in range(i+1, N):
        xj, hj = XH[j]
        if xj <= scp_end:
            if hj > 0:
                XH[j][1] -= dmg
        else:
            break
    
#    print(XH)

# output
print(ans)


Fixed submission:
from collections import deque

# input
N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]

# process
XH.sort()
#print(XH)

ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:
#        print("x,h,dam: {},{},{}".format(x,h,dam))
        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))
#    print("x,h,dam,ans,dq: {},{},{},{},{}".format(x,h,dam,ans,dq))
    
# output
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math

# input
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

# process
XH.sort()

ans = 0
for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue

    XH[i][1] = 0
    c = math.ceil(h/A)
    ans += c

    dmg = A*c
    scp_end = x+D*2

    for j in range(i+1, N):
        xj, hj = XH[j]
        if xj <= scp_end:
            if hj > 0:
                XH[j][1] -= dmg
        else:
            break
    
# output
print(ans)


Fixed submission:
from collections import deque

# input
N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]

# process
XH.sort()
#print(XH)

ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:
#        print("x,h,dam: {},{},{}".format(x,h,dam))
        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))
#    print("x,h,dam,ans,dq: {},{},{},{},{}".format(x,h,dam,ans,dq))
    
# output
print(ans)
Buggy python submission (verdict: Runtime Error):
import fractions

def lcm(l):
    if len(l) == 1:
        return l[0]

    t = l[0]
    for i in range(1, len(l)):
        t = (t * l[i]) // fractions.gcd(t, l[i])
    return t

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

# process/output
a = lcm(A)

if a/2 > M: 
    print(0)

else:
    print(int(M/a-0.5)+1)


Fixed submission:
from functools import reduce
from fractions import gcd

def lcm(l):
    if len(l) == 1:
        return l[0]

    t = l[0]
    for i in range(1, len(l)):
        t = (t * l[i]) // gcd(t, l[i])
    return t

# input
N, M = map(int, input().split())
A = list(map(lambda x: x//2, map(int, set(input().split()))))

# process
ans = 0
lc = lcm(A)

if lc <= M:
    f = True
    for a in A:
        if lc//a%2 == 0:
            f = False
            break

    if f:
        ans = int(M/lc-1)//2+1

# output
print(ans)

Buggy python submission (verdict: Runtime Error):
import math

def lcm(l):
    if len(l) == 1:
        return l[0]

    t = l[0]
    for i in range(1, len(l)):
        t = (t * l[i]) // math.gcd(t, l[i])
    return t

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

# process
a = lcm(A)
p = int(M/a-0.5)

# output
if p == 0: print(0)
else: print(p+1)


Fixed submission:
from functools import reduce
from fractions import gcd

def lcm(l):
    if len(l) == 1:
        return l[0]

    t = l[0]
    for i in range(1, len(l)):
        t = (t * l[i]) // gcd(t, l[i])
    return t

# input
N, M = map(int, input().split())
A = list(map(lambda x: x//2, map(int, set(input().split()))))

# process
ans = 0
lc = lcm(A)

if lc <= M:
    f = True
    for a in A:
        if lc//a%2 == 0:
            f = False
            break

    if f:
        ans = int(M/lc-1)//2+1

# output
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#sys.setrecursionlimit(10**5)
MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort(reverse=True)
ans = 0

if N == 1:
    ans = C[0]
else:
    for i in range(N):
        ans += C[i]*(2+i)*2**(N-2)
        
# output
print(ans*2**N%MOD)


Fixed submission:
#import sys
#sys.setrecursionlimit(10**5)
MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort(reverse=True)
ans = 0

if N == 1:
    ans = C[0]*2**N
else:
    for i in range(N):
        ans += C[i]*(2+i)

    ans *= 4**(N-1)

# output
print(ans%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)

MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort()
ans = 0

# d:数列S、Tの異なる整数の数、idx:加算するコストの開始インデックス
def f(d, idx):
    if d == 0 or d + idx > N:
        return 1, 0

    t = 0
    cnt = 0
    for i in range(idx, N-d+1):
        c, r = f(d-1, i+1)
        t += d*C[i]*c + r
        cnt += c

    
    return cnt, t

ans = 0
for i in range(1, N+1):
    c, r = f(i, 0)
    ans += r
#    print("ans,r: {},{}".format(ans,r))

# output
print(ans*2**N%MOD)


Fixed submission:
#import sys
#sys.setrecursionlimit(10**5)
MOD = 10**9+7

# input
N = int(input())
C = list(map(int, input().split()))
    
# process
C.sort(reverse=True)
ans = 0

if N == 1:
    ans = C[0]*2**N
else:
    for i in range(N):
        ans += C[i]*(2+i)

    ans *= 4**(N-1)

# output
print(ans%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#sys.setrecursionlimit(10**7)
#from functools import reduce
#from fractions import gcd


# input
n, m = map(int, list(input().split()))
alist = list(map(int, input().split()))

# process
blist=[]
for i in alist:
    for j in alist:
        blist.append(i+j)

blist.sort(reverse=True)

ans = 0
for i in range(m):
    ans += blist[i]    

# output
print(ans)

Fixed submission:
# input
N, M = map(int, list(input().split()))
A = list(map(int, input().split()))

# process
A.sort(reverse=True)

# 1回の握手の幸福度がx以上となるものの数、幸福度の合計を求める
def calc(x):
    count, sum = 0, 0

    j, t = 0, 0
    for i in reversed(range(N)):
        while j < N and A[i]+A[j] >= x:
            t += A[j]
            j += 1
        count += j
        sum += A[i]*j + t
    
    return (count, sum)

# 2分探索で答えを求める
def binary_search(x, y):
    mid = (x+y)//2

    count, sum = calc(mid)
    
    if count < M:
        return binary_search(x, mid)
    else:
        if x == mid:
            print(sum-(count-M)*mid)
        else:
            return binary_search(mid, y)

# 実行
binary_search(0, A[0]*2+1)
Buggy python submission (verdict: Runtime Error):
from math import gcd

# input
a , b = map(int, list(input().split()))

# output
print(int(a*b/gcd(a, b)))


Fixed submission:
from fractions import gcd

# input
a , b = map(int, list(input().split()))

# output
print(int(a*b/gcd(a, b)))
Buggy python submission (verdict: Time Limit Exceeded):
# input
n = int(input())
alist = list(map(int, list(input().split())))

# process/output
if not 1 in alist:
    print(-1)

else:
    ans = 0
    i = 1
    while len(alist) > 0:
        if i in alist:
            index = alist.index(i)
            alist = alist[index+1:]
            ans += index
            i += 1
            
        else:
            ans += len(alist)
            break
        
    print(ans)


Fixed submission:
# input
n = int(input())
alist = list(map(int, input().split()))

# process/output
if not 1 in alist:
    print(-1)

else:
    i = 1
    for j in range(n):
        if alist[j] == i:
            i+=1
                    
    print(n-i+1)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from functools import reduce

# input
n = int(input())
alist = list(map(int, input().split()))

# processing
l = []

i = 0
while i < n-1:
    j = i + 1
    while j < n:
        l.append(alist[i]^alist[j])
        j+=1
    i+=1

# output
print(reduce(lambda x, y: x+y, l) % (10**9+7))


Fixed submission:
# -*- coding: utf-8 -*-

# input
n = int(input())
alist = list(map(int, input().split()))

# process
result = 0
for bit in range(60):
    m = 1 << bit
    c = sum(a & m for a in alist) >> bit
    result += (c * (n - c)) << bit
    result %= 10**9+7

# output
print(result)
Buggy python submission (verdict: Runtime Error):
from math import gcd

# inputa
n , x , d = map(int, list(input().split()))

# process
if d == 0:
    if x == 0:
        print(1)
    else:
        print(n + 1)

else:
    # sが何通りあるかを求める
    
    # dを正にする
    if d < 0: d, x = -d, -x

    # d,xを互いに素にする   
    g = gcd(d, abs(x))
    d, x =  d//g, x//g
    
    # s=k*x+c*d
    # cは最小で0からk-1の和、最大でn-kからn-1の和
    # kを固定するとs//dは1ずつの単調増加なので、最小と最大で個数が分かる

    # sはs%d=k*x%dなので、それで分類する
    # →klistをk*x%dでソート
    klist = list(range(n + 1))
    klist.sort(key=lambda k: (k*x%d, k))

    # kを固定し、cの最小・最大を求め、加算していく
    ans = 0

    # 1つ前の値を保持
    pmin, pmax = 1, 0
    pmd = -1
    for k in klist:
        # s//dの最小・最大・s%d
        tmin = (k * x + (k - 1) * k // 2 * d) // d
        tmax = (k * x + (2 * n - k - 1) * k // 2 * d) // d
        tmd = k*x%d

        # s%dが前と同じ　かつ
        # s//dの最小<=前の最大　かつ　s//dの最大>=前の最小のとき
        # 最大・最小を更新
        if tmd == pmd and tmin <= pmax and tmax >= pmin:
            pmin, pmax = min(pmin, tmin), max(pmax, tmax)
        else:
            ans += pmax - pmin + 1
            pmin, pmax = tmin, tmax
        pmd = tmd
        #print(k, l, r, pl, pr, ans)
    
    ans += pmax - pmin + 1
    print(ans)


Fixed submission:
from fractions import gcd

# inputa
n , x , d = map(int, list(input().split()))

# process
if d == 0:
    if x == 0:
        print(1)
    else:
        print(n + 1)

else:
    # sが何通りあるかを求める
    
    # dを正にする
    if d < 0: d, x = -d, -x

    # d,xを互いに素にする   
    g = gcd(d, abs(x))
    d, x =  d//g, x//g
    
    # s=k*x+c*d
    # cは最小で0からk-1の和、最大でn-kからn-1の和
    # kを固定するとs//dは1ずつの単調増加なので、最小と最大で個数が分かる

    # sはs%d=k*x%dなので、それで分類する
    # →klistをk*x%dでソート
    klist = list(range(n + 1))
    klist.sort(key=lambda k: (k*x%d, k))

    # kを固定し、cの最小・最大を求め、加算していく
    ans = 0

    # 1つ前の値を保持
    pmin, pmax = 1, 0
    pmd = -1
    for k in klist:
        # s//dの最小・最大・s%d
        tmin = (k * x + (k - 1) * k // 2 * d) // d
        tmax = (k * x + (2 * n - k - 1) * k // 2 * d) // d
        tmd = k*x%d

        # s%dが前と同じ　かつ
        # s//dの最小<=前の最大　かつ　s//dの最大>=前の最小のとき
        # 最大・最小を更新
        if tmd == pmd and tmin <= pmax and tmax >= pmin:
            pmin, pmax = min(pmin, tmin), max(pmax, tmax)
        else:
            ans += pmax - pmin + 1
            pmin, pmax = tmin, tmax
        pmd = tmd
        
    ans += pmax - pmin + 1
    print(ans)
Buggy python submission (verdict: Runtime Error):
# input
n = int(input())

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

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)


Fixed submission:
# input
s = input()

# process
week = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
windex = week.index(s)
ans = 7 if windex == 0 else 7-windex

# output
print(ans)
Buggy python submission (verdict: Runtime Error):
# input
n = int(input())

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

# process
ans = [0 for i in range(n-1)]

def f(pa, c):
    color = 1
    for pb in edge[pa]:
        if color == c: color += 1
        ans[pb[1]] = color 
        f(pb[0], color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

# input
n = int(input())

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

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
# input
n = int(input())

edge = [[0, 0, 0] for i in range(n-1)]
for i in range(n-1):
    edge[i][0] ,edge[i][1] = map(int, list(input().split()))

# process
k = 0
pcolors = [0 for i in range(n)]
for i in range(n):
    color = 0
    for j in range(n-1):
        if edge[j][0] == i+1:
            color += 1
            if color == pcolors[i]: color += 1

            edge[j][2] = color
            pcolors[edge[j][1]-1] = color
            if k < color: k = color
    

# output
print(k)
for e in edge:
    print(e[2])

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

# input
n = int(input())

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

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
# input
n = int(input())

edge = [[0, 0, 0] for i in range(n-1)]
for i in range(n-1):
    edge[i][0] ,edge[i][1] = map(int, list(input().split()))

# process
def findcolor(p):
    if p == 1: 
        return 0
    else: 
        for e in edge:
            if e[1] == p:
                return e[2]

for i in range(n):
    i += 1
    color = 0
    pcolor = findcolor(i)
    for j in range(n-1):
        if edge[j][0] == i:
            color += 1
            if color == pcolor: color += 1
            edge[j][2] = color

k = 0
for e in edge:
    if e[2] > k: k = e[2]

# output
print(k)
for e in edge:
    print(e[2])

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

# input
n = int(input())

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

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
import math
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
 
a,b,c = listint()
if a+b+2*math.sqrt(a*b) < c:
    print('Yes')
else:
    print('No')
import math
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

a,b,c = listint()
if math.sqrt(a)+math.sqrt(b) < math.sqrt(c):
    print('Yes')
else:
    print('No')

Fixed submission:
a,b,c = input().split()
a = int(a)
b = int(b)
c = int(c)

if 4*a*b < (c - a - b)*(c-a-b) and a + b< c:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
a = input().split()
if a[0] == a[1] == a[2]:
  print('No')
else:
  print('Yes')

Fixed submission:
a = input()
if a[0] == a[1] and a[1] == a[2]:
  print('No')
else:
  print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):

def main(s,perse):
    query = input().split()
    query[0] = int(query[0])
    if query[0] == 1:
        return s,-perse
    else:
        query[1] = int(query[1])
        if query[1] == 1:
            if perse == 1:
                s.insert(0,query[2])
            else:
                s.append(query[2])
        if query[1] == 2:
            if perse == -1:
                s.insert(0,query[2])
            else:
                s.append(query[2])
        return s,perse
def conv(s):
    a = []
    for i in range(len(s)):
        a.append(s[i])
    return a

s = input()
s = conv(s)
q = int(input())
perse = 1
for i in range(q):
    s,perse = main(s,perse)
if perse == -1:
    s.reverse()
print(''.join(s))

Fixed submission:
def main(s,end,start,perse):
    start.reverse()
    start.append(''.join(s))
    start.append(''.join(end))
    if perse == -1:
        start.reverse()
    print(''.join(start))
def conv(s):
    a = []
    for i in range(len(s)):
        a.append(s[i])
    return a
perse = 1
start = []
end = []
  
s = input()
q = int(input())
for i in range(q):
    query = input().split()
    query[0] = int(query[0])
    if query[0] == 1:
        perse = -perse
    else:
        query[1] = int(query[1])
        if (int(query[1])*2-3)*perse == 1:
            end.append(query[2])
        else:
            start.append(query[2])
s =  conv(s)
if perse == -1:
    s.reverse()
    end.reverse()
main(s,end,start,perse)
Buggy python submission (verdict: Time Limit Exceeded):
def jud(a,b):
    dic = ['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']
    if len(a) == 0:
        return 0
    if len(b) == 0:
        return 1
    if a[0] == b[0]:
        return jud(a[1:],b[1:])
    if dic.index(a[0]) > dic.index(b[0]):
        return 1
    if dic.index(a[0]) < dic.index(b[0]):
        return 0
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
def megsort(s):
    p = len(s)
    if p == 1:
        return s
    else:
        q = int(p/2)
        left = megsort(s[q:])
        right = megsort(s[:q])
        arr = []
        while len(left)*len(right) != 0:
            if jud(left[0],right[0]) == 1:
                arr.append(right.pop(0))
                
            else:
                arr.append(left.pop(0))
        if len(left) == 0:
            arr.extend(right)
        else:
            arr.extend(left)
        return arr
        

n = int(input())
s = []
for i in range(n):
    s.append(input())
s = megsort(s)
ans = 1
ansar = [s[0]]
now = 1
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        now = now +1
    else:
        now = 1
    if now == ans:
        ansar.append(s[i+1])
    if now > ans:
        ans = now
        ansar = [s[i+1]]
for i in range(len(ansar)):
    print(ansar[i])

Fixed submission:
n = int(input())
s = []
for i in range(n):
    s.append(input())
s.sort()
ans = 1
ansar = [s[0]]
now = 1
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        now = now +1
    else:
        now = 1
    if now == ans:
        ansar.append(s[i+1])
    if now > ans:
        ans = now
        ansar = [s[i+1]]
for i in range(len(ansar)):
    print(ansar[i])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input().strip())
A = list(map(int, input().strip().split()))

def mod(x):
	return x % 1000000007

s = 0
for i in range(N - 1):
	s = mod(s + A[i] * sum(A[i + 1:]))

print(s)

Fixed submission:
N = int(input().strip())
A = list(map(int, input().strip().split()))

def mod(x):
	return x % 1000000007

sa = sum(A[1:])
s = mod(A[0] * sa)

for a in A[1:-1]:
	sa -= a
	s = mod(s + a * sa)

print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input().strip())
A = list(map(int, input().strip().split()))

mod = lambda x: x % 1000000007
s = 0

for i in range(N - 1):
	for j in range(i + 1, N):
		s = mod(s + A[i] * A[j])

print(s)

Fixed submission:
N = int(input().strip())
A = list(map(int, input().strip().split()))

def mod(x):
	return x % 1000000007

sa = sum(A[1:])
s = mod(A[0] * sa)

for a in A[1:-1]:
	sa -= a
	s = mod(s + a * sa)

print(s)
Buggy python submission (verdict: Runtime Error):
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

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

AdivisibleC = (A - 1) // C
AdivisibleD = (A - 1) // D
AdivisibleCD = (A - 1) // lcm(C, D)
AindivisibleCD = (A - 1) - (AdivisibleC + AdivisibleD - AdivisibleCD)

BdivisibleC = B // C
BdivisibleD = B // D
BdivisibleCD = B // lcm(C, D)
BindivisibleCD = B - (BdivisibleC + BdivisibleD - BdivisibleCD)

print(BindivisibleCD - AindivisibleCD)

Fixed submission:
from fractions import gcd

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

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

AdivisibleC = (A - 1) // C
AdivisibleD = (A - 1) // D
AdivisibleCD = (A - 1) // lcm(C, D)
AindivisibleCD = (A - 1) - (AdivisibleC + AdivisibleD - AdivisibleCD)

BdivisibleC = B // C
BdivisibleD = B // D
BdivisibleCD = B // lcm(C, D)
BindivisibleCD = B - (BdivisibleC + BdivisibleD - BdivisibleCD)

print(BindivisibleCD - AindivisibleCD)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
c = input()

wi = c.find('W')
ri = c.rfind('R')

if wi == -1 or ri == -1:
    print(0)
else:
    ans = 0
    while wi < ri:
        s = list(c)
        s[wi] = 'R'
        s[ri] = 'W'
        c = ''.join(s)
        wi = c.find('W')
        ri = c.rfind('R')
        ans += 1

    print(ans)

Fixed submission:
n = int(input())
c = input()

wi = c.find('W')
ri = c.rfind('R')

if wi == -1 or ri == -1:
    print(0)
else:
    ans = 0
    while wi < ri:
        wi += 1
        wi = c[wi:].find('W') + wi
        ri = c[:ri].rfind('R')
        ans += 1

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
q = int(input())

m = {}
for i in a:
    if i in m.keys():
        m[i] = m[i] + 1
    else:
        m[i] = 1

for i in range(q):
    b, c = map(int,input().split())
    if b in m.keys():
        if c in m.keys():
            m[c] = m[c] + m[b]
        else:
            m[c] = m[b]
        m.pop(b)
    ans = 0
    for k in m:
        ans += m[k] * k
    print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
q = int(input())

m = {}
for i in a:
    if i in m.keys():
        m[i] = m[i] + 1
    else:
        m[i] = 1

ans = 0
for k in m:
    ans += m[k] * k

for i in range(q):
    b, c = map(int,input().split())
    if b in m.keys():
        t = 0
        if c in m.keys():
            t = m[c] * c
            m[c] = m[c] + m[b]
        else:
            m[c] = m[b]
        ans += m[c] * c - m[b] * b - t
        m.pop(b)
    print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
q = int(input())

m = {}
for i in a:
    if i in m.keys():
        m[i] = m[i] + 1
    else:
        m[i] = 1

for i in range(q):
    b, c = map(int,input().split())
    m[c] = m[c] + m[b]
    m.pop(b)
    ans = 0
    for k in m:
        ans += m[k] * k
    print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
q = int(input())

m = {}
for i in a:
    if i in m.keys():
        m[i] = m[i] + 1
    else:
        m[i] = 1

ans = 0
for k in m:
    ans += m[k] * k

for i in range(q):
    b, c = map(int,input().split())
    if b in m.keys():
        t = 0
        if c in m.keys():
            t = m[c] * c
            m[c] = m[c] + m[b]
        else:
            m[c] = m[b]
        ans += m[c] * c - m[b] * b - t
        m.pop(b)
    print(ans)