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

n=int(input())
a=list(map(int, input().split()))
for i in range(1,n+1):
    print(a.count(i))


### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split()))
a=collections.Counter(a)
for i in range(1,n+1):
    print(a.get(i, 0))
### BUGGY CODE ###

import itertools
import numpy as np
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = np.ones((W,H)).astype(np.bool)
for p in bk:
	mat[p] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1,y]:
			mat[x-1,y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1,y]:
			new.append((x+1,y))
			mat[x+1,y] = False
		if y > 0 and mat[x,y-1]:
			new.append((x,y-1))
			mat[x,y-1] = False
		if y < H-1 and mat[x,y+1]:
			new.append((x,y+1))
			mat[x,y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)




### FIXED CODE ###

H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = [[True]*H for i in [0]*W]
for x,y in bk:
	mat[x][y] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1][y]:
			mat[x-1][y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1][y]:
			new.append((x+1,y))
			mat[x+1][y] = False
		if y > 0 and mat[x][y-1]:
			new.append((x,y-1))
			mat[x][y-1] = False
		if y < H-1 and mat[x][y+1]:
			new.append((x,y+1))
			mat[x][y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = input().split(" ")

sum = 1
for i in range(n):
  sum = sum * int(a[i])

if sum > 1000000000000000000:
  print(-1)
else:
  print(sum)

### FIXED CODE ###

n = int(input())
a = input().split(" ")

sum = 1
for i in a:
  sum = sum * int(i)
  if sum > 1000000000000000000:
    break

if "0" in a:
  print(0)
elif sum > 1000000000000000000:
  print(-1)
else:
  print(sum)
### BUGGY CODE ###

import heapq


def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n  #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d


################################
n, x, y = map(int, input().split())  #n:頂点数
w = n
edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w - 1):
    edge[i + 1].append([1, i])
    edge[i].append([1, i + 1])
edge[x - 1].append([1, y - 1])
edge[y - 1].append([1, x - 1])

dic = {i: 0 for i in range(1, n)}

# cost = [[float("inf") for i in range(n)] for i in range(n)]
# #cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
# for i in range(w - 1):
#     cost[i + 1][i] = 1
#     cost[i][i + 1] = 1
# cost[x - 1][y - 1] = 1
# cost[y - 1][x - 1] = 1

for i in range(n):
    tmp = dijkstra_heap(i)
    zero = False
    for j in tmp:
        if zero:
            dic[j] += 1
        if j == 0:
            zero = True

for i in range(1, n):
    print(dic[i])


### FIXED CODE ###

n, x, y = map(int, input().split())

dic = {i: 0 for i in range(1, n)}
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        dist = min(j - i, abs(i - x) + abs(j - y) + 1)
        dic[dist] += 1


for i in range(1, n):
    print(dic[i])
### BUGGY CODE ###

N, X, Y = map(int, input().split())
dic = {}


def Warshall_Floyd(N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


d = [[float("inf")] * N for i in range(N)]

for i in range(N-1):
    d[i][i + 1] = 1
    d[i + 1][i] = 1

for i in range(N):
    d[i][i] = 0

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

d = Warshall_Floyd(N)


for i in range(N):
    for j in range(N):
        if dic.get(d[i][j]) is None:
            dic[d[i][j]] = 1
        else:
            dic[d[i][j]] += 1

for i in range(1, N):
    if dic.get(i) is None:
        print(0)
    else:
        print(dic[i]//2)

### FIXED CODE ###

N, X, Y = map(int, input().split())
d = {}


for i in range(1, N):
    for j in range(i+1, N+1):
        m = min(j-i, abs(X-i) + 1 + abs(Y-j))
        if d.get(m) is None:
            d[m] = 1
        else:
            d[m] += 1

for i in range(1, N):
    if d.get(i) is None:
        print(0)
    else:
        print(d[i])
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

max_score = -float('inf')

for i in range(n):
    loop_score_array = []
    loop_score = 0
    loop_len = 0
    pos = i
    while True:
        pos = p[pos] - 1
        loop_score += c[pos]
        loop_score_array.append(loop_score)
        loop_len+=1
        if pos == i:
            break
    for i, score in enumerate(loop_score_array):
        if k-i-1 < 0:
            continue
        loop_num = (k-i-1)//loop_len
        score_sum = score + max(0, loop_score)*loop_num
        max_score = max(score_sum, max_score)
print(max_score)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

max_score = -float('inf')

for i in range(n):
    loop_score_array = []
    loop_score = 0
    loop_len = 0
    pos = i
    while True:
        pos = p[pos] - 1
        loop_score += c[pos]
        loop_score_array.append(loop_score)
        loop_len+=1
        if pos == i:
            break
    for i, score in enumerate(loop_score_array):
        if k-i-1 < 0:
            continue
        loop_num = (k-i-1)//loop_len
        score_sum = score + max(0, loop_score)*loop_num
        max_score = max(score_sum, max_score)
print(max_score)
### BUGGY CODE ###

N,M = map(int,input().split())
to = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a].append(b)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Stack = [(start,0)] #今の点、何歩目か
visit = [[INF,INF,INF] for _ in range(N)] #三歩目、一歩目、二歩目
visit[start][0] = 0
while Stack: #今の点、けんけんぱのどれか、一個前に止まった点
  v,step = Stack.pop()
  now = visit[v][step]
  step = (step+1)%3 #ここでstep+1歩目でvへ行く
  for w in to[v]:
    #print(visit[w][step],step,now)
    if visit[w][step] <= now:
      continue
    Stack.append((w,step)) #step歩目でwにいて次vへ行く。
    if step %3 == 0:
      visit[w][step] = min(visit[w][step],now+1)
    else:
      visit[w][step] = min(visit[w][step],now)
#print(visit)
if visit[end][0] == INF:
  ans = -1
else:
  ans = visit[end][0]
print(ans)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
to = [[] for _ in range(N*3)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  to[a*3].append(b*3+1)
  to[a*3+1].append(b*3+2)
  to[a*3+2].append(b*3)
start,end = map(int,input().split())
start -= 1;end -= 1
#print(to)
INF = float("inf")
Q = deque([start*3])
visit = [INF for _ in range(N*3)]
visit[start*3] = 0
while Q:
  v = Q.popleft()
  for w in to[v]:
    if visit[w] != INF:
      continue
    visit[w] = visit[v]+1
    if w == end*3:
      print(visit[w]//3)
      exit()
    Q.append(w) #step歩目でwにいて次vへ行く。

#print(visit)
if visit[end*3] == INF:
  ans = -1
else:
  ans = visit[end*3]//3
print(ans)
### BUGGY CODE ###

import sys

n=int(input())
l=[]
for i in range(n):
    l.append(input())
alp=[chr(_) for _ in range(97,97+26)]
res=[]
ans=0

for j in l:
    ll=list(j)
    tmp=[0]*26
    for k in ll:
        m=0
        for x in alp:
            if k==x:
                tmp[m]+=1
            m+=1
    aa="".join(map(str,tmp))
    res.append(aa)

for y in res:
    tmp2=0
    for z in res:
        if y==z:
            tmp2+=1
    ans+=tmp2-1

print(int(ans/2))

### FIXED CODE ###

import sys

n=int(input())
l=["".join(sorted(sys.stdin.readline().strip())) for i in range(n)]


res={}
ans=0
 
for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    if aa in res:
        ans+=res[aa]
        res[aa]+=1
    else:
        res[aa]=1

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

from collections import deque
N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
result = a.count(-1)

leaves = {i for i in range(N) if a[i] > -1} - set(a)
dq = deque()
append = dq.append
for i in leaves:
    v = i
    l = 0
    while a[v] != -1 and l < K:
        append(v)
        l += 1
        v = a[v]

print(result+len(set(dq)))

### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

visited = set()
add = visited.add
startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += (v not in visited)
        add(v)
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            if v not in visited:
                result += 1
                add(v)
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)
### BUGGY CODE ###

import itertools

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

sum=0
mod = 1000000007

def permod(x):
  return x%mod
B = list(map(permod,A))

for v in itertools.combinations(B, 2):
    sum +=v[0]*v[1]
    sum = sum %mod
print(sum)

### FIXED CODE ###

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

mod= 10**9+7

A = sum(a)

ans=0

for i in a:
  A -= i
  A%=mod
  ans += A*i
  ans%=mod
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())

for i in range(n, m + 1):
    if m % i == 0:
        print(int(m / i))
        break

### FIXED CODE ###

n, m = map(int, input().split())
p = int(m / n)

if n > 100:
    for i in range(p, 0, -1):
        if m % i == 0:
            print(i)
            break
else:
    for i in range(n, m + 1):
        if m % i == 0:
            print(int(m / i))
            break
### BUGGY CODE ###

import math
#n,m = 3,2
#a = [4,1,5]
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
for i,ai in enumerate(a):
    if i == 0:
        b[i] = ai % m
    else:
        b[i] = (ai + b[i-1]) % m

ans = 0

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

for i in range(m):
    c = b.count(i)    
    if c >= 2:
        ans += combinations_count(c,2)
ans += b.count(0)

print(ans)


### FIXED CODE ###

import math
import collections

#n,m = 3,2
#a = [4,1,5]
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
for i,ai in enumerate(a):
    if i == 0:
        b[i] = ai % m
    else:
        b[i] = (ai + b[i-1]) % m

ans = 0

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

c = collections.Counter(b)
for i in c.values():
    if i >= 2:
        ans += combinations_count(i,2)

#for i in range(m):
#    c = b.count(i)    
#    if c >= 2:
#        ans += combinations_count(c,2)
ans += b.count(0)

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

a,b,k = map(int,input().split())
     
for i in range(k):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
     
print(str(a) + " " + str(b))

### FIXED CODE ###

A, B, K = map(int,input().split())

A -= K
if(A < 0):
    B -= abs(A)
    A = 0
    if(B < 0):
        B = 0

print(str(A) + " " + str(B))
### BUGGY CODE ###

import math,time
N = int(input())
S = input()
# length = len(S)
ans = 0
t1 = time.time()
for i in range(1000):
    locknum = str(i).zfill(3)
    digit = 0
    for j in range(N):
        if digit<2 and locknum[digit] == S[j]:
            digit +=1
        elif digit==2 and locknum[digit]==S[j]:
            ans +=1
            break

    # a = S.find(locknum[0])
    # b = S.find(locknum[1],a+1)
    # c = S.find(locknum[2],b+1)
    # if a!=-1 and b!=-1 and c!=-1:
    #     # print(i)
    #     ans +=1

t2 = time.time()
# print(t2-t1)                 
print(ans)




                    



### FIXED CODE ###

import math,time
N = int(input())
S = input()
# length = len(S)
ans = 0
t1 = time.time()
for i in range(1000):
    locknum = str(i).zfill(3)
    a = S.find(locknum[0])
    b = S.find(locknum[1],a+1)
    c = S.find(locknum[2],b+1)
    if a!=-1 and b!=-1 and c!=-1:
        # print(i)
        ans +=1

t2 = time.time()
# print(t2-t1)                 
print(ans)
### BUGGY CODE ###

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

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    G[ai-1].append(bi-1)
    G[bi-1].append(ai-1)

L=[]
for i in G:
    L.append(len(i))

K=max(L)
print(K)

k=[[0]*K for i in range(N)]

from collections import deque

q=deque([0])
C=[[-1]*N for i in range(N)]

while q:
    x=q.popleft()
    for i in G[x]:
        if C[x][i]!=-1:continue
        for j in range(K):
            if k[x][j]==0:
                C[x][i]=j
                C[i][x]=j
                k[x][j]=1
                k[i][j]=1
                break
        q.append(i)

for i in range(N-1):
    print(C[a[i]][b[i]]+1)




### FIXED CODE ###

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

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    G[ai-1].append(bi-1)
    G[bi-1].append(ai-1)

k=[0]*N

from collections import deque

q=deque([0])
visited=[0]*N
ans={}
p=[-1]*N

kmx=0
while q:
    x=q.popleft()
    visited[x]=1
    cnt=1
    for i in G[x]:
        if visited[i]!=0:continue
        if p[x]==cnt:
            cnt+=1
        ans[(x,i)]=cnt
        ans[(i,x)]=cnt

        p[i] = cnt
        cnt += 1
        kmx=max(kmx,cnt-1)
        q.append(i)

print(kmx)
for i in range(N-1):
    print(ans[(a[i],b[i])])
### BUGGY CODE ###

from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
visited = [False]*(H*W)
q = deque()

for i in range(H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            q.append((i, j, 0))
            visited[i*W+j] = True

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and visited[ny*W+nx] == False:
            visited[ny*W+nx] = True
            q.append((ny, nx, lv+1))

print(res)


### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)
### BUGGY CODE ###

import collections
n,*a=map(int,open(0).read().split())
b=[0]*n
b[0]=a[0]
for i in range(1,n):
    b[i]=b[i-1]+a[i]
b.sort()    
c=set(b)
ans=b.count(0)
for i in c:
    j=b.count(i)
    ans+=j*(j-1)//2
print(ans)

### FIXED CODE ###

import collections
n,*a=map(int,open(0).read().split())
b=[0]*n
b[0]=a[0]
for i in range(1,n):
    b[i]=b[i-1]+a[i]
b.sort()    
b=[0]+b
ans=0
l=collections.Counter(b)
for i in l.values():
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = []
dp = [int(0) for _ in range(N+1)]
dp[0] = 1
dp[1] = 1
MOD = 1000000007
for _ in range(M):
    A.append(int(input()))
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % MOD
    
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

n,y=map(int,input().split())
an=-1,-1,-1
for m in range(n+1):
    for g in range(n+1):
        for s in range(n+1):
            if m+g+s == n and 10000*m+5000*g+1000*s ==y:
                print(m,g,s)
                exit(0)
print(*an)


### FIXED CODE ###

n,y=map(int,input().split())
an=-1,-1,-1
for m in range(n+1):
    for g in range(n+1):
        s=n-m-g
        if m+g >n:
            break
        if m+g+s == n and 10000*m+5000*g+1000*s ==y:
            print(m,g,s)
            exit(0)

print(*an)
### BUGGY CODE ###

S = input()
s = list(S)
if len(s) == 1:
    print("1")
else:
    num_list = [s[:i].count("B") if s[i] == "W" else 0 for i in range(1, len(s))]
    print(str(sum(num_list)))

### FIXED CODE ###

s = list("BWBWBW" * 10000)

s = list(input())
ret, counter = 0, 0
for a in s:
    if a == "B":
        counter += 1
    else:
        ret += counter
print(str(ret))
### BUGGY CODE ###

from sys import stdin

sN, sQ = stdin.readline().split()
N, Q = int(sN), int(sQ)
# print(N,Q)
S = stdin.readline().rstrip()
data = [stdin.readline().split() for itr in range(Q)]
# print(data)

for itr in range(Q):
    l = int(data[itr][0]) - 1 
    r = int(data[itr][1])
    s = S[l:r]
    # print(s)
    print(s.count('AC'))

### FIXED CODE ###

from sys import stdin

sN, sQ = stdin.readline().split()
N, Q = int(sN), int(sQ)
# print(N,Q)
S = stdin.readline().rstrip()
data = [stdin.readline().split() for itr in range(Q)]
# print(data)

grid = [None] * N
# print(grid)
count = 0
for num in range(N):
    if num == 0:
        grid[num] = count
        continue
    if S[num] == 'C' and S[num-1] == 'A':
        count += 1
        grid[num] = count
        continue
    grid[num] = count

# print(grid)

for itr in range(Q):
    l = int(data[itr][0]) - 1
    r = int(data[itr][1]) - 1
    # print(grid[r],grid[l])
    print(grid[r]-grid[l])
### BUGGY CODE ###

for i in range(4*10**10):
  print(i)

### FIXED CODE ###

S = input()
T = input()

flag = 0
for i in range(len(S)):
  if S[i] == T[i]:
    continue
  flag = 1

if flag == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from collections import deque

N,M = map(int,input().split())

data = [[] for _ in range(3*N)]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    data[3*u].append(3*v+1)
    data[3*u+1].append(3*v+2)
    data[3*u+2].append(3*v)

S,T = map(int,input().split())
S -= 1
T -= 1

inf = 10**6
stack = deque([[3*S,0]])
time = [inf] * (3*N)

while stack:
    x = stack.pop()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)

### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())

data = [[] for _ in range(3*N)]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    data[3*u].append(3*v+1)
    data[3*u+1].append(3*v+2)
    data[3*u+2].append(3*v)

S,T = map(int,input().split())
S -= 1
T -= 1

inf = 10**6
stack = deque([[3*S,0]])
time = [inf] * (3*N)

while stack:
    x = stack.popleft()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    candidateA = []
    weightA = 0
    tmp_A = N
    for idx, a in enumerate(A):
        if weightA + a > K:
            tmp_A = idx
            break
        else:
            weightA += a
    candidateA = A[:tmp_A]
    max_count = current_count = len(candidateA)

    #candidateB = []
    weightB = 0
    terminated = False
    for b in B:
        if terminated == True and weightA + weightB > K:
            break

        if len(candidateA)==0 and weightA + weightB + b > K:
            break

        if weightA + weightB + b <= K:
            weightB += b
            #candidateB.append(b)
            current_count += 1

        elif terminated==False:
            while weightA + weightB + b > K:
                if len(candidateA)>0:
                    weightA -= candidateA.pop()
                    current_count -= 1
                else:
                    terminated=True

            if weightA + weightB + b <= K:
                weightB += b
                #candidateB.append(b)
                current_count += 1
        max_count = max(max_count, current_count)

    print(max_count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, K, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = [0]*(10**5+1)
for i in range(10**5+1):
    index[i] = lsn.count(i)
sum1 = sum(lsn)
for l in ls2:
    sum1 = sum1 +(l[1]-l[0])*index[l[0]]
    index[l[1]] += index[l[0]]
    index[l[0]] = 0
    print(sum1)

### FIXED CODE ###

import collections
N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = collections.Counter(lsn)
sum1 = sum(lsn)
for l in ls2:
    sum1 = sum1 +(l[1]-l[0])*index[l[0]]
    index[l[1]] += index[l[0]]
    index[l[0]] = 0
    print(sum1)