Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# 反転させて扱いやすくしておく S[i]は10^iの個数を表すようになる
S = input()[::-1]

MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)

# 10^i%13を求める
def mod13_of_10pow(i):
    return [1, 10, 9, 12, 3, 4][i % 6]


# ans[k] : 13で割った余りがkになる数の個数
# 最後のans[5]が答えになる
ans = [modint(0)] * 13

for i, c in enumerate(S):
    if i == 0:
        if c != '?':
            ans[int(c)] += 1
        else:
            for q in range(10):
                ans[q] += 1
        continue

    tmp = [modint(0)] * 13

    m = mod13_of_10pow(i)
    ds = [int(c)] if c != '?' else [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for d in ds:
        for k in range(13):
            tmp[(k + d * m) % 13] += ans[k]

    ans = tmp

print(ans[5])


Fixed submission:
# 反転させて扱いやすくしておく S[i]は10^iの個数を表すようになる
S = input()[::-1]

MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)

# 10^i%13を求める
def mod13_of_10pow(i):
    return [1, 10, 9, 12, 3, 4][i % 6]


# ans[k] : 13で割った余りがkになる数の個数
# 最後のans[5]が答えになる
ans = [modint(0)] * 13

for i, c in enumerate(S):
    if i == 0:
        if c != '?':
            ans[int(c)] += 1
        else:
            for q in range(10):
                ans[q] += 1
        continue

    tmp = [modint(0)] * 13

    m = mod13_of_10pow(i)
    ds = [int(c)] if c != '?' else [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for d in ds:
        for k in range(13):
            tmp[(k + d * m) % 13] += ans[k]

    ans = tmp

print(ans[5])
Buggy python submission (verdict: Runtime Error):
n, a, b, c, d = map(int, input().split())
s = input()


if a > b:
    a, b, c, d = b, a, d, c

def search(start, goal):
    for i in range(start+1, goal - 2):
        if s[i] + s[i + 1] == '##': return False
    return True


def search3(start, goal):
    for i in range(start, goal -3):
        if s[i] + s[i + 1]+[i+2] == '...': return True
    return False
if c < b:
    if search(a,c) and search(b,d):print('Yes')
    else:print('No')

else:
    if search3(b-1,d+1):print('Yes')
    else:print('No')


Fixed submission:
n, a, b, c, d = map(int, input().split())
s = input()

a,b,c,d=a-1,b-1,c-1,d-1
if a > b:
    a, b, c, d = b, a, d, c


if '##' in s[a:c] or '##' in s[b:d]:print('No')
else:
    if c < d:
        print('Yes')

    else:
        if '...' in s[b - 1 : d + 2]:
            print('Yes')
        else:
            print('No')

Buggy python submission (verdict: Runtime Error):
n, a, b, c, d = map(int, input().split())
s = input()


if a > b:
    a, b, c, d = b, a, d, c

def search(start, goal):
    for i in range(start+1, goal - 2):
        if s[i] + s[i + 1] == '##': return False
    return True


def search3(start, goal):
    for i in range(start, goal -2):
        if s[i] + s[i + 1]+[i+2] == '...': return True
    return False
if c < b:
    if search(a,c) and search(b,d):print('Yes')
    else:print('No')

else:
    if search3(b-1,d+1):print('Yes')
    else:print('No')


Fixed submission:
n, a, b, c, d = map(int, input().split())
s = input()

a,b,c,d=a-1,b-1,c-1,d-1
if a > b:
    a, b, c, d = b, a, d, c


if '##' in s[a:c] or '##' in s[b:d]:print('No')
else:
    if c < d:
        print('Yes')

    else:
        if '...' in s[b - 1 : d + 2]:
            print('Yes')
        else:
            print('No')
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
l = [(hoge.append(gcd(hoge[i-1], a[i])), hoge)[1] for hoge in [[a[0]]] for i in range(1, n)][0]
r = reversed([(hoge.append(gcd(hoge[i-1], a[n-i-i])), hoge)[1] for hoge in [[a[0]]]for i in range(1, n)][0])
print (reduce(lambda x,y:max(x,y),[gcd(l[i-1]if 0<i else r[i+1],r[i+1] if i<n-1 else l[i-1])for i in range(n)]))

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

from fractions import gcd

tl = [a[0]]
for i in range(1, n):
    tl.append(gcd(tl[i - 1], a[i]))

tr = [a[n - 1]]
for i in range(1, n):
    tr.append(gcd(tr[i - 1], a[n - 1 - i]))
tr.reverse()

ans = 1
for i in range(n):
    tmp = 1
    if i == 0: tmp = tr[i + 1]
    elif i == n - 1: tmp = tl[i - 1]
    else: tmp = gcd(tl[i - 1], tr[i + 1])
    ans = max(ans, tmp)
print(ans)

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

from fractions import gcd

tl = [a[0]]
for i in range(1, n):
    tl.append(gcd(tl[i - 1], a[i]))

tr = [a[n - 1]]
for i in range(1, n):
    tr.append(gcd(tr[i - 1], a[n - 1 - i]))
tr.reverse()

ans = 1
for i in range(n):
    tmp = 1
    l = tl[i - 1] if 0 < i else tr[i + 1]
    r = tr[i + 1] if i < n - 1 else tl[i - 1]
    ans = max(gcd(l,r))
print(ans)


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

from fractions import gcd

tl = [a[0]]
for i in range(1, n):
    tl.append(gcd(tl[i - 1], a[i]))

tr = [a[n - 1]]
for i in range(1, n):
    tr.append(gcd(tr[i - 1], a[n - 1 - i]))
tr.reverse()

ans = 1
for i in range(n):
    tmp = 1
    if i == 0: tmp = tr[i + 1]
    elif i == n - 1: tmp = tl[i - 1]
    else: tmp = gcd(tl[i - 1], tr[i + 1])
    ans = max(ans, tmp)
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 2:
    print(a[1])
else:
    dif = set()
    for i in range(n - 1):
        dif.append(a[i - 1] - a[i])
    d = list(dif)
    d.sort()
    d.reverse()
    f=False
    for i in range(len(d)):
        if d[i] == 0:
            break
        ok = True
        flag = False
        for j in range(n):
            if a[j] % d[i] != 0:
                if flag:
                    break
                else:
                    ok=False
        if ok:
            f=True
            print(i)
            break
    if not f:
        print(1)

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

from fractions import gcd

tl = [a[0]]
for i in range(1, n):
    tl.append(gcd(tl[i - 1], a[i]))

tr = [a[n - 1]]
for i in range(1, n):
    tr.append(gcd(tr[i - 1], a[n - 1 - i]))
tr.reverse()

ans = 1
for i in range(n):
    tmp = 1
    if i == 0: tmp = tr[i + 1]
    elif i == n - 1: tmp = tl[i - 1]
    else: tmp = gcd(tl[i - 1], tr[i + 1])
    ans = max(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))


AB = [a + b for a in A for b in B]
AB.sort()
AB = AB[-K:]

ans = [ab + c for ab in AB for c in C]
ans.sort()

for x in ans[-K:][::-1]:
    print(x)


Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))


AB = [a + b for a in A for b in B]
AB.sort()
AB = AB[-K:]

ans = [ab + c for ab in AB for c in C]
ans.sort()

for x in ans[-K:][::-1]:
    print(x)
Buggy python submission (verdict: Runtime Error):
8 1000 800 100
300
333
400
444
500
555
600
666

Fixed submission:
N, A, B, C = map(int, input().split())
l = []
for i in range(N):
    l.append(int(input()))
ans = 100000000


def rec(a, b, c, d):
    if d == N:
        if a[1] > 0 and b[1] > 0 and c[1] > 0:
            global ans
            ans = min(
                ans,
                abs(
                    a[0] - A) + abs(b[0] - B) + abs(c[0] - C)
                + 10 * (a[1] + b[1] + c[1] - 3)
            )
        return
    rec((a[0] + l[d], a[1] + 1), b, c, d + 1)
    rec(a, (b[0] + l[d], b[1] + 1), c, d + 1)
    rec(a, b, (c[0] + l[d], c[1] + 1), d + 1)
    rec(a, b, c, d + 1)


rec((0, 0), (0, 0), (0, 0), 0)
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
# a.sort()
# now = a[0]
# for i in range(1, n):
#     if (a[i] % now != 0):
#         now = a[i] % now
# print(now)
import math
from functools import reduce
print(reduce(math.gcd,a))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
# a.sort()
# now = a[0]
# for i in range(1, n):
#     if (a[i] % now != 0):
#         now = a[i] % now
# print(now)
import fractions
from functools import reduce
print(reduce(fractions.gcd,a))
Buggy python submission (verdict: Runtime Error):
n = int(input())
v = list(map(int, input().split()))

vv = [[], []]
for i in range(n):
    vv[i % 2].append(v[i])

import collections
items0 = sorted(collections.Counter(vv[0]).items(), key=lambda x: -x[1])
items1 = sorted(collections.Counter(vv[1]).items(), key=lambda x: -x[1])
key0 = [x[0] for x in items0]
key1 = [x[0] for x in items1]
val0 = [x[1] for x in items0]
val1 = [x[1] for x in items1]

if key0[0] == key1[0]:
    if len(items0) == 1:
        print(n//2)
    else:
        print(min(n - val0[0] - val1[1], min(n - val0[1] - val1[0])))
else:
    print(n - val0[0] - val1[0])


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

vv = [[], []]
for i in range(n):
    vv[i % 2].append(v[i])

import collections
items0 = sorted(collections.Counter(vv[0]).items(), key=lambda x: -x[1])
items1 = sorted(collections.Counter(vv[1]).items(), key=lambda x: -x[1])
key0 = [x[0] for x in items0]
key1 = [x[0] for x in items1]
val0 = [x[1] for x in items0]
val1 = [x[1] for x in items1]

ans = n - val0[0] - val1[0]

if key0[0] == key1[0]:
    tmp0=tmp1=1000000000000000
    if len(items0) > 1:
        tmp0 = n - val0[1] - val1[0]
    if len(items1) > 1:
        tmp1 = n - val0[0] - val1[1]
    ans = min(tmp0, tmp1)
    if len(items0) == 1 and len(items1) == 1:
        ans=n//2
print(ans)

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

vv = [[], []]
for i in range(n):
    vv[i % 2].append(v[i])

import collections
items0 = sorted(collections.Counter(vv[0]).items(), key=lambda x: -x[1])
items1 = sorted(collections.Counter(vv[1]).items(), key=lambda x: -x[1])
key0 = [x[0] for x in items0]
key1 = [x[0] for x in items1]
val0 = [x[1] for x in items0]
val1 = [x[1] for x in items1]

if key0[0] = ! key1[0]:
    if len(items0) == 1:
        print(n//2)
    else:
        print(min(n - val0[0] - val1[1], min(n - val0[1] - val1[0])))
else key0[0] != key1[0]:
    print(n - val0[0] - val1[0])


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

vv = [[], []]
for i in range(n):
    vv[i % 2].append(v[i])

import collections
items0 = sorted(collections.Counter(vv[0]).items(), key=lambda x: -x[1])
items1 = sorted(collections.Counter(vv[1]).items(), key=lambda x: -x[1])
key0 = [x[0] for x in items0]
key1 = [x[0] for x in items1]
val0 = [x[1] for x in items0]
val1 = [x[1] for x in items1]

ans = n - val0[0] - val1[0]

if key0[0] == key1[0]:
    tmp0=tmp1=1000000000000000
    if len(items0) > 1:
        tmp0 = n - val0[1] - val1[0]
    if len(items1) > 1:
        tmp1 = n - val0[0] - val1[1]
    ans = min(tmp0, tmp1)
    if len(items0) == 1 and len(items1) == 1:
        ans=n//2
print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
t = input()
# snum = []
# tnum = []
# for c in range(ord('a'), ord('z') + 1):
#     snum.append([i for i, x in enumerate(s) if x == chr(c)])
# for c in range(ord('a'), ord('z') + 1):
#     tnum.append([i for i, x in enumerate(t) if x == chr(c)])
# snum.sort()
# tnum.sort()
# print('Yes' if snum == tnum else 'No')


sn=[0 for i in range(26)]
tn=[0 for i in range(26)]
for i in range(len(s)):
    sn[ord(s[i])]+=1
    tn[ord(t[i])]+=1
print('Yes' if sorted(sn) == sorted(tn) else 'No')



Fixed submission:
s = input()
t = input()
snum = []
tnum = []
for c in range(ord('a'), ord('z') + 1):
    snum.append([i for i, x in enumerate(s) if x == chr(c)])
for c in range(ord('a'), ord('z') + 1):
    tnum.append([i for i, x in enumerate(t) if x == chr(c)])
snum.sort()
tnum.sort()
print('Yes' if snum == tnum else 'No')
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

aa = [a[i] - i for i in range(n)]
aa.sort()

print(min(aa[n//2]))

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

aa = [a[i] - i-1 for i in range(n)]
aa.sort()


def f(b):
    return sum([abs(a-b)for a in aa])

print(f(aa[n//2]))
Buggy python submission (verdict: Runtime Error):
n,k=map(int, input().split())
a=map(int, input().split())
print(N-K+1)

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(1, n, k - 1):
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

s = ['#' * (W + 2)] + ['#' + input() + '#' for i in range(H)] + ['#' * (W + 2)]

# m : そこにたどり着くために必要な白マスの数
m = [[-1 for x in range(W+2)] for y in range(H+2)]
m[1][1] = 1


from collections import deque
qx = deque([1])
qy = deque([1])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


while len(qx) > 0:
    x, y = qx.popleft(), qy.popleft()
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]

        # 訪れたことがあるなら調べない
        if m[nx][ny] != -1: continue

        if s[ny][nx] == '.':
            qx.append(nx), qy.append(ny)
            m[ny][nx] = m[y][x] + 1

if m[H][W] == -1:
    print(-1)

else:
    print(sum([c.count('.') for c in s]) - m[H][W])



Fixed submission:
H, W = map(int, input().split())

s = ['#' * (W + 2)] + ['#' + input() + '#' for i in range(H)] + ['#' * (W + 2)]

# m : そこにたどり着くために必要な白マスの数
m = [[-1 for x in range(W+2)] for y in range(H+2)]
m[1][1] = 1


from collections import deque
qx = deque([1])
qy = deque([1])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


while len(qx) > 0:
    x, y = qx.popleft(), qy.popleft()
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]
        # 訪れたことがあるなら調べない
        if m[ny][nx] != -1: continue

        if s[ny][nx] == '.':
            qx.append(nx), qy.append(ny)
            m[ny][nx] = m[y][x] + 1

if m[H][W] == -1:
    print(-1)

else:
    print(sum([c.count('.') for c in s]) - m[H][W])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = 0
r = n-1

def get(i):
	print(i)
	s = input()
	if s == 'Vacant':
		exit()
	return s


def kind(i):
	return i%2 ^ get(i)=='Male'

while True:
	kl = kind(l)
	kr = kind(r)
	m = (l+r)//2
	if kind(m)==kl:
		l = m
	else:
		r = m



Fixed submission:
n = int(input())
l = 0
r = n-1

def get(i):
	print(i)
	s = input()
	if s == 'Vacant':
		exit()
	return s


def kind(i):
	return (i%2) ^ (get(i)=='Male')


kl = kind(l)
kr = kind(r)

while True:
	m = (l+r)//2
	km = kind(m)
	if km==kl:
		l, kl = m, km
	else:
		r, kr = m, km
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()

x, y = 0, 0

i = 0
while i < n - 1:
    if a[i] == a[i + 1]:
        x = a[i]
        i += 2
        break
    i += 1
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()

x, y = 0, 0

i = 0
while i < n - 1:
    if a[i] == a[i + 1]:
        x = a[i]
        i += 2
        break
    i += 1

while i < n - 1:
    if a[i] == a[i + 1]:
        y = a[i]
        i += 2
        break
    i += 1
print(x * y)
while i < n - 1:
    if a[i] == a[i + 1]:
        y = a[i]
        i += 2
        break
    i += 1
print(x * y)

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

x, y = 0, 0

i = 0
while i < n - 1:
    if a[i] == a[i + 1]:
        x = a[i]
        i += 2
        break
    i += 1

while i < n - 1:
    if a[i] == a[i + 1]:
        y = a[i]
        i += 2
        break
    i += 1
print(x * y)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
ans = [[0 for x in range(w)] for y in range(h)]

def getx(i):
    return i // h
def gety(i):
    return i % h if i // (2 * h) < h else h - (i % h)

aa=[]
for i in range(n):
    aa += [i + 1 for _ in range(a[i])]

for i in range(h * w):
    ans[gety(i)][getx(i)] = aa[i]

for y in range(h):
    for x in range(w):
        if x > 0: print(' ', end='')
        print(ans[y][x], end='')
    print()

Fixed submission:
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
ans = [[0 for x in range(w)] for y in range(h)]

def getx(i):
    return i // h
def gety(i):
    if (i % (2 * h)) < h:
        return i % h
    else:
        return h - i % h - 1

aa=[]
for i in range(n):
    aa += [i + 1 for _ in range(a[i])]

for i in range(h * w):
    ans[gety(i)][getx(i)] = aa[i]

for y in range(h):
    for x in range(w):
        if x > 0: print(' ', end='')
        print(ans[y][x], end='')
    print()
Buggy python submission (verdict: Runtime Error):
a = 1
while a*2 <= int(input()):
    a*=2
print(a)

Fixed submission:
a = 1
n=int(input())
while a*2 <= n:
    a*=2
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
    ans.append(a[i])
    ans.reverse()
print(' '.join(map(str, ans)))

Fixed submission:
n = int(input())
a = input().split()
ans=[]
if n%2==0:
    for i in range(n - 1, -1, -2):
        ans.append(a[i])
    for i in range(0, n, 2):
        ans.append(a[i])
else:
    for i in range(n - 1, -1, -2):
        ans.append(a[i])
    for i in range(1, n, 2):
        ans.append(a[i])
print(' '.join(ans))
Buggy python submission (verdict: Runtime Error):
 print(''.join(i[0] for i in input().split()).upper())

Fixed submission:
s = input().split()
print(''.join(i[0] for i in s).upper())
Buggy python submission (verdict: Runtime Error):
#1,1,1 -> (1,1) 1

#1,2,3 -> (1,3) 2

#1,1,3 -> (1,3) 1  <=> 1,1,3,3 -> (1,3) 1,3

#1,2,1,3,7 == [1:2, 2:1, 3:1, 7:1]
#[1:4, 2:3, 3:2, 5:1, 6:2, 8:2, 11:1]

#それぞれ1または2と等しい
#[1:2, 2:1, 3:2, 5:1, 6:2, 8:2, 11:1]
#[1,1,3,3,6,6,8,8]
#[1,1,3,6,6,8,8]
#[1,3,6,8]

N = int(input())
A = list(map(int, input().split()))
B = [-1 for i in range(100005)]

for i in range(N):
    if B[A[i]] == -1:
        B[A[i]] = 1
    elif B[A[i]] == 1:
        B[A[i]] = 2:
    elif B[A[i]] == 2:
        B[A[i]] = 1

n = N - B.count(-1)

if B.count(2) % 2 == 0:
    print(n)
else:
    print(n-1)


Fixed submission:
#1,1,1 -> (1,1) 1

#1,2,3 -> (1,3) 2

#1,1,3 -> (1,3) 1  <=> 1,1,3,3 -> (1,3) 1,3

#1,2,1,3,7 == [1:2, 2:1, 3:1, 7:1]
#[1:4, 2:3, 3:2, 5:1, 6:2, 8:2, 11:1]

#それぞれ1または2と等しい
#[1:2, 2:1, 3:2, 5:1, 6:2, 8:2, 11:1]
#[1,1,3,3,6,6,8,8]
#[1,1,3,6,6,8,8]
#[1,3,6,8]

N = int(input())
A = list(map(int, input().split()))
B = [-1 for i in range(100005)]

for i in range(N):
    if B[A[i]] == -1:
        B[A[i]] = 1
    elif B[A[i]] == 1:
        B[A[i]] = 2
    elif B[A[i]] == 2:
        B[A[i]] = 1

n = len(B) - B.count(-1)

if B.count(2) % 2 == 0:
    print(n)
else:
    print(n-1)
Buggy python submission (verdict: Time Limit Exceeded):
import collections

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

counter = collections.Counter(al)

for _ in range(q):
  b, c = [int(i) for i in input().split()]
  count = counter[b]
  counter[b] = 0
  counter[c] += count
  total = 0
  for (v, c) in counter.most_common():
    total += v * c
  print(total)

Fixed submission:
import collections

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

counter = collections.Counter(al)

total = 0
for (v, c) in counter.most_common():
  total += v * c
for _ in range(q):
  b, c = [int(i) for i in input().split()]
  count = counter[b]
  counter[b] = 0
  counter[c] += count
  total = total + (c - b) * count
  print(total)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
al = [int(i) for i in input().split()]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors[:-1]
  
import collections

if n == 1:
  print(1)
else:
  total = 0
  ss = set(al)
  c = collections.Counter(al)
  for num in al:
    if c[num] >= 2:
      continue
    for d in make_divisors(num):
      if d in ss:
        break
    else:
      total += 1
  print(total)



Fixed submission:
n = int(input())
al = [int(i) for i in input().split()]  
al.sort()
ma = al[-1]
from collections import Counter
c = Counter(al)

if n == 1:
  print(1)
else:
  sn = set()
  total = 0
  l = len(al)
  for num in al:
    if num in sn:
      continue
    if c[num] == 1:
      total += 1
    tmp = num
    while tmp <= ma:
      sn.add(tmp)
      tmp += num
  print(total)
Buggy python submission (verdict: Runtime Error):
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []
s_keiro = set()

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    break
  s_keiro.add(index)
  keiro.append(index)

pos = (k-start) % mod
print(keiro[start + pos - 1]+1)

Fixed submission:
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []
s_keiro = set()
loop_f = False

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    loop_f = True
    break
  s_keiro.add(index)
  keiro.append(index)

if loop_f:
  pos = (k-start-1) % mod
  if mod == 1:
    print(keiro[start]+1)
  else:
    print(keiro[start + pos]+1)
else:
  print(keiro[-1] + 1)

Buggy python submission (verdict: Runtime Error):
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []
s_keiro = set()

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    break
  s_keiro.add(index)
  keiro.append(index)

print(keiro[start + (k-start)%mod - 1]+1)

Fixed submission:
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []
s_keiro = set()
loop_f = False

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    loop_f = True
    break
  s_keiro.add(index)
  keiro.append(index)

if loop_f:
  pos = (k-start-1) % mod
  if mod == 1:
    print(keiro[start]+1)
  else:
    print(keiro[start + pos]+1)
else:
  print(keiro[-1] + 1)

Buggy python submission (verdict: Runtime Error):
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []

for i in range(k):
  index = al[index] - 1
  keiro.append(index)
  if keiro.count(index) == 2:
    start = keiro.index(index)
    mod = i - start
    break

print(keiro[k%mod-1]+1)

Fixed submission:
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []
s_keiro = set()
loop_f = False

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    loop_f = True
    break
  s_keiro.add(index)
  keiro.append(index)

if loop_f:
  pos = (k-start-1) % mod
  if mod == 1:
    print(keiro[start]+1)
  else:
    print(keiro[start + pos]+1)
else:
  print(keiro[-1] + 1)