Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
import math
import fractions
def input(): return sys.stdin.readline().rstrip()

def main():
    a, b, c, d = map(int, input().split())
    def count_ab(n):
        return math.floor(b / n) - math.ceil(a / n) + 1
    c_cnt = count_ab(c)
    d_cnt = count_ab(d)
    cd_cnt = count_ab(c * d // fractions.gcd(c, d))

    print(b - a - c_c - d_c + cd_c + 1)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
import fractions
def input(): return sys.stdin.readline().rstrip()

def main():
    a, b, c, d = map(int, input().split())
    cd_gcd = c * d // fractions.gcd(c, d)
    cnt = lambda n: n - n // c - n // d + n // cd_gcd
    print(cnt(b) - cnt(a-1))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 1000000007
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    dp = [0] * (n+1)
    dp[:2] = 1, 1 if 1 not in a else 0

    for i in range(2, n+1):
        if i not in a:
            dp[i] += (dp[i-1] + dp[i-2]) % MOD
    print(dp[-1])

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def pl(n):
    if n > 0:
        return n
    else:
        return 0

def main():
    MOD = 1000000007
    n, m = map(int, input().split())

    dp = [0] * (n+1)
    dp[0] = 1
    
    for _ in range(m):
        dp[int(input())] = -1

    for i in range(1, n+1):
        if dp[i] < 0:
            continue
        dp[i] += pl(dp[i-1])
        if i >= 2:
            dp[i] += pl(dp[i-2])
        dp[i] %= MOD
    print(max(dp[-1], 0))

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 1000000007
    n, m = map(int, input().split())

    a = []
    pre = -10
    for _ in range(m):
        i = int(input())
        if i == pre + 1:
            print(0)
            quit()
        a.append(i)
        pre = i

    dp = [0] * (n+1)
    dp[0] = 1
    for i in range(1, n+1):
        if i in a:
            continue
        dp[i] += dp[i-1]
        if i >= 2:
            dp[i] += dp[i-2]
        dp[i] %= MOD
    print(dp[-1])

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def pl(n):
    if n > 0:
        return n
    else:
        return 0

def main():
    MOD = 1000000007
    n, m = map(int, input().split())

    dp = [0] * (n+1)
    dp[0] = 1
    
    for _ in range(m):
        dp[int(input())] = -1

    for i in range(1, n+1):
        if dp[i] < 0:
            continue
        dp[i] += pl(dp[i-1])
        if i >= 2:
            dp[i] += pl(dp[i-2])
        dp[i] %= MOD
    print(max(dp[-1], 0))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    _, m = map(int, input().split())

    l, r = map(int, input().split())
    ans = [i for i in range(l, r+1)]
    for _ in range(m-1):
        l, r = map(int, input().split())
        ans = [i for i in ans if l <= i <= r]
    print(len(ans))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    _, m = map(int, input().split())

    max = -1
    min = 10 ** 5 + 1
    for _ in range(m):
        l, r = map(int, input().split())
        if l > max:
            max = l
        if r < min:
            min = r
    if min - max < 0:
        print(0)
    else:
        print(min - max + 1)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    _, m = map(int, input().split())

    l, r = map(int, input().split())
    ans = {i for i in range(l, r+1)}
    for _ in range(m-1):
        l, r = map(int, input().split())
        ans &= {i for i in range(l, r+1)}
    print(len(ans))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    _, m = map(int, input().split())

    max = -1
    min = 10 ** 5 + 1
    for _ in range(m):
        l, r = map(int, input().split())
        if l > max:
            max = l
        if r < min:
            min = r
    if min - max < 0:
        print(0)
    else:
        print(min - max + 1)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())

    graph = [[-1 for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        graph[u][v] = w
        graph[v][u] = w

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in enumerate(graph[x]):
            if depth[i] > -1 or g == -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())

    graph = defaultdict(lambda : defaultdict(int))
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        graph[u][v] = w
        graph[v][u] = w

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in graph[x].items():
            if depth[i] > -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    UVW = [tuple(map(int, input().split())) for _ in range(N - 1)]

    ans = ['0'] * N
    fixed = set()
    for u, v, w in UVW:
        if w % 2 == 1:
            if u in fixed:
                ans[v] = '1'
            else:
                ans[u] = '1'
            fixed.add(u)
            fixed.add(v)
    print("\n".join(ans))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())

    graph = defaultdict(lambda : defaultdict(int))
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        graph[u][v] = w
        graph[v][u] = w

    depth = [-1] * (N)
    depth[0] = 0
    def dfs(x):
        for i, g in graph[x].items():
            if depth[i] > -1:
                continue
            depth[i] = depth[x] + g
            dfs(i)
    dfs(0)
    print("\n".join(['1' if d % 2 == 0 else '0' for d in depth]))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
from itertools import groupby
def input(): return sys.stdin.readline().rstrip()

def main():
    N, K = map(int, input().split())
    S = input()

    ans = 0
    l = 0
    que = deque()
    que_sum = 0
    for k, v in groupby(S):
        if k == '0':
            l0 = len(tuple(v))
            que.append(l + l0)
            if len(que) > K:
                que.popleft()
            que_sum = sum(que)
        else:
            l = len(tuple(v))
            que_sum += l
        if que_sum > ans:
            ans = que_sum
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
from collections import deque
from itertools import groupby
def input(): return sys.stdin.readline().rstrip()

def main():
    _, K = map(int, input().split())
    S = input()

    ans = 0
    l = 0
    que = deque()
    que_sum = 0
    for k, v in groupby(S):
        if k == '0':
            l0 = len(tuple(v))
            que_sum += l0
            que.append(l + l0)
            if len(que) > K:
                que_sum -= que.popleft()
        else:
            l = len(tuple(v))
            que_sum += l
        if que_sum > ans:
            ans = que_sum
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = []
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            AB.append(a + b)
    AB = sorted(AB, reverse=True)[:K]

    ans = []
    for i, ab in enumerate(AB):
        for j, c in enumerate(C):
            ans.append(ab + c)
    ans = sorted(ans, reverse=True)[:K]
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = [a + b for a in A for b in B]
    AB = sorted(AB, reverse=True)[:K]

    ABC = [ab + c for ab in AB for c in C]
    ABC = sorted(ABC, reverse=True)[:K]
    for i in ABC:
        print(i)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = [0] * (X*Y)
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            AB[i * Y + j] = a + b
    
    ans = [0] * (X*Y*Z)
    for i, ab in enumerate(AB):
        for j, c in enumerate(C):
            ans[i * Z + j] = ab + c
    ans = sorted(ans, reverse=True)[:K]
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, Z, K = map(int, input().split())
    A, B, C = [sorted(map(int, input().split())) for _ in range(3)]

    AB = [a + b for a in A for b in B]
    AB = sorted(AB, reverse=True)[:K]

    ABC = [ab + c for ab in AB for c in C]
    ABC = sorted(ABC, reverse=True)[:K]
    for i in ABC:
        print(i)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    ini_len = len(S)

    ind0 = 1
    ind1 = 1
    while ind0 >= 0 or ind1 >= 0:
        ind0 = S.find('01')
        if ind0 >= 0:
            S = S.replace('01', '')
        ind1 = S.find('10')
        if ind1 >= 0:
            S = S.replace('10', '')
    print(ini_len - len(S))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    print(len(S) - abs(S.count('1') - S.count('0')))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = np.array([int(i) for i in input().split()])
    b = np.array([int(i) for i in input().split()])

    if a.sum() < b.sum():
        print(-1)
        exit()

    diff = a - b
    org_diff = np.array(diff)

    def move(num):
        max_i = np.argmax(diff)
        max_v = diff[max_i]
        if max_v > num:
            diff[max_i] -= num
        else:
            diff[max_i] = 0
            move(num - max_v)

    for i in range(n):
        if diff[i] >= 0:
            continue
        move(-diff[i])
        diff[i] = 0
    diff -= org_diff
    print(sum([1 for i in diff if i != 0]))
    
if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    B = map(int, input().split())

    sum = 0
    ans = 0
    rest = []
    for a, b in zip(A, B):
        if b > a:
            sum += b - a
            ans += 1
        else:
            rest.append(a - b)
    rest.sort(reverse=True)

    if sum <= 0:
        print(0)
        exit()

    for r in rest:
        sum -= r
        ans += 1
        if sum <= 0:
            break
    if sum > 0:
        print(-1)
    else:
        print(ans)
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))

    a_sum = sum(a)
    if a_sum < sum(b):
        print(-1)
        exit()

    diff = [0] * n
    for i in range(n):
        diff[i] = a[i] - b[i]
    org_diff = diff[:]

    def move(num):
        max_v = max(diff)
        max_i = diff.index(max_v)
        if max_v > num:
            diff[max_i] -= num
        else:
            diff[max_i] = 0
            move(num - max_v)

    for i in range(n):
        if diff[i] >= 0:
            continue
        move(-diff[i])
        diff[i] = 0
    print(sum([1 for i in range(n) if diff[i] != org_diff[i]]))
    
if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    B = map(int, input().split())

    sum = 0
    ans = 0
    rest = []
    for a, b in zip(A, B):
        if b > a:
            sum += b - a
            ans += 1
        else:
            rest.append(a - b)
    rest.sort(reverse=True)

    if sum <= 0:
        print(0)
        exit()

    for r in rest:
        sum -= r
        ans += 1
        if sum <= 0:
            break
    if sum > 0:
        print(-1)
    else:
        print(ans)
    
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [10 ** 9] * n
dp[0] = 0

for i in range(1, n):
    k_max = min(i, k)
    for j in range(1, k_max+1):
        dp[i] = min(dp[i], abs(h[i] - h[i-j]) + dp[i-j])
print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [10 ** 9] * n
dp[0] = 0

for i in range(1, n):
    k_max = min(i, k)
    for j in range(1, k_max+1):
        dp[i] = min(dp[i], abs(h[i] - h[i-j]) + dp[i-j])
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

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

    for max_w in range(W+1):
        for i, (w, v) in enumerate(items):
            if max_w - w >= 0:
                dp[i+1][max_w] = max(dp[i][max_w], dp[i][max_w-w] + v)
            else:
                dp[i+1][max_w] = dp[i][max_w]
    print(dp[N][W])

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

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

    for max_w in range(W+1):
        for i, (w, v) in enumerate(items):
            if max_w - w >= 0:
                dp[i+1][max_w] = max(dp[i][max_w], dp[i][max_w-w] + v)
            else:
                dp[i+1][max_w] = dp[i][max_w]
    print(dp[N][W])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    s = input()
    t = input()

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

    for i in range(slen):
        for j in range(tlen):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    ans = ''
    while slen > 0 and tlen > 0:
        if dp[slen][tlen] == dp[slen - 1][tlen]:
            slen -= 1
        elif dp[slen][tlen] == dp[slen][tlen - 1]:
            tlen -= 1
        else:
            slen -= 1
            tlen -= 1
            ans += s[slen]
    print(ans[::-1])

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    s = input()
    t = input()

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

    for i in range(slen):
        for j in range(tlen):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    ans = ''
    while slen > 0 and tlen > 0:
        if dp[slen][tlen] == dp[slen - 1][tlen]:
            slen -= 1
        elif dp[slen][tlen] == dp[slen][tlen - 1]:
            tlen -= 1
        else:
            slen -= 1
            tlen -= 1
            ans += s[slen]
    print(ans[::-1])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    K = int(input())
    if S[K-1] == '1':
        print('1')
    for i in list(S):
        if i != '1':
            print(i)
            exit()
    print('1')

if __name__ == '__main__':
    main()



Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    K = int(input())
    if len(S) > K and S[K-1] == '1':
        print('1')
        exit()
    for i in list(S):
        if i != '1':
            print(i)
            exit()
    print('1')

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    yen = [6 ** i for i in range(1, 7)]
    yen += [9 ** i for i in range(1, 6)]
    yen = [i for i in yen if i <= N]
    yen.sort(reverse=True)

    def MIN(a, b):
        if a > b:
            return b
        else:
            return a

    @lru_cache(maxsize=None)
    def dfs(x, n, m):
        n += 1
        for y in yen:
            if n >= m:
                return n
            if y > x:
                continue
            if x - y < 6:
                return n + x - y
            m = MIN(dfs(x - y, n, m), m)
        return m

    print(dfs(N, 0, N))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    yen = [6 ** i for i in range(1, 7)]
    yen += [9 ** i for i in range(1, 6)]
    yen = [i for i in yen if i <= N]
    yen.sort(reverse=True)

    def MIN(a, b):
        if a > b:
            return b
        else:
            return a

    @lru_cache(maxsize=None)
    def dfs(x, n, m):
        n += 1
        for y in yen:
            if n >= m:
                return n
            if y > x:
                continue
            if x - y < 6:
                return n + x - y
            m = MIN(dfs(x - y, n, m), m)
        return m

    print(dfs(N, 0, N))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    S = list(input())

    ans = 10 * 6
    for i in range(N):
        tmp = S[:i].count('W')
        if i + 1< N:
            tmp += S[i+1:].count('E')
        ans = min(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    S = list(input())

    ans = 10 ** 6
    sum_count = S.count('E')
    for s in S:
        aft = 0
        if s == 'W':
            aft = 1
        else:
            sum_count -= 1
        ans = min(ans, sum_count)
        sum_count += aft
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * (n + 1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]

def main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    train = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.union(p, q)
    
    for _ in range(L):
        r, s = map(int, input().split())
        train.union(r, s)
    
    ans = [1] * (N + 1)
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if road.same(i, j) and train.same(i, j):
                ans[i] += 1
                ans[j] += 1
    for i in ans[1:]:
        print(i)    

if __name__ == '__main__':
    main()


Fixed submission:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * (n + 1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]

def main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    train = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.union(p, q)
    
    for _ in range(L):
        r, s = map(int, input().split())
        train.union(r, s)
    
    ans = []
    counter = defaultdict(int)
    for i in range(1, N + 1):
        root = (road.find(i), train.find(i))
        ans.append(root)
        counter[root] += 1
    for i in range(1, N + 1):
        root = (road.find(i), train.find(i))
        print(counter[root])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import bisect
import numpy as np
import math
from collections import deque
from collections import defaultdict
from math import gcd

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
S = np.sum(A)
for a in A:
    cnt[a] += 1

Q = int(input())

for _ in range(Q):
    b, c = map(int, input().split())
    num_of_b = cnt[b]
    S -= num_of_b * b
    S += num_of_b * c
    cnt[c] += num_of_b

    print(S)



Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
cnt = defaultdict(int)
S = sum(A)
for a in A:
    cnt[a] += 1

Q = int(input())

for _ in range(Q):
    b, c = map(int, input().split())
    num_of_b = cnt[b]
    S += num_of_b * c - num_of_b * b
    cnt[c] += num_of_b
    cnt[b] -= num_of_b

    print(S)