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

import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(hcnt)
wmax = max(wcnt)
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)


### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
def dfs(u, prev, ans):
    # result : {k: (kを通ってuで終わるパスの数=kを通らないと到達できない頂点数)}, (u以下の部分木のサイズ)
    k = cs[u]
    if len(ns[u])==1 and prev in ns[u]:
        eend, ss = {k : 1}, 1
    else:
        ss = 1
        eend = defaultdict(int)
        for v in ns[u]:
            if v==prev:
                continue
            end, s = dfs(v, u, ans)
            ss += s
            tmp = s - end.get(k, 0)
            ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
            for kk,vv in end.items():
                if kk!=k:
                    eend[kk] += end[kk]
        eend[k] = ss
#     print(eend, ss, ans)
    return eend, ss
    
end, s = dfs(1, -1, ans)
for k in range(1, n+1):
    if k==cs[0]:
        continue
    tmp = s - end.get(k, 0)
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

from collections import Counter
n, m = list(map(int, input().split()))
ll = []

for i in range(m):
    l, r = list(map(int, input().split()))
    ll.extend(range(l,r+1))

ans = 0
c = Counter(ll)
for k, v in c.items():
    if v == m:
        ans = ans + 1
print(ans)


### FIXED CODE ###

from collections import Counter
n, m = list(map(int, input().split()))
ll = []
x = 0
y = 10 ** 5

for i in range(m):
    l, r = list(map(int, input().split()))
    x, y = max(x, l), min(y, r)

s = (y - x) + 1
if s < 0:
    s = 0
print(s)
### BUGGY 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):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

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

    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)


### 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 sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
for i in range(n):
    pro *= (i+1)
print(pro%mod)

### FIXED CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())

print(math.factorial(n)%mod)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
output = []
for _ in range(q):
    l, r = map(int, input().split())
    sub_s = s[l-1:r]
    ans = sub_s.count("AC")
    output.append(ans)
for i in range(q):
    print(output[i])


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac_count = [0]
ac_num = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_num += 1
    ac_count.append(ac_num)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_count[r-1] - ac_count[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    l[0] = 0
    ans = -100

    for i in range(n):
        a[i] -= 1

    for i in range(n*3):
        k -= 1
        now = a[now] #転送された場所
        l[now] += 1
        if l[now] == 2: #3ループ目の頭
            loop = l.count(1) + 1
            k %= loop
        if k == 0:
            ans = now + 1
            break

    print(max(ans, -1))

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()
### BUGGY CODE ###

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

### FIXED CODE ###

a, b ,c= input().split()
a = int(a)
b = int(b)
c = int(c)
d = a - c
if d < 0:
    a = 0
    e = b + d
    if e < 0:
        b = 0
    else:
        b = b + d
else:
    a = a - c
print(str(a)+" "+str(b))
### BUGGY CODE ###

import math

ans = []
while True:
	try:
		n = int(raw_input())
		isPrime = [False, False]
		for i in range(n - 1):
			isPrime.append(True)
		i = 2
		while i < math.sqrt(n):
			j = i * 2
			while j < len(isPrime):
				isPrime[j] = False
				j += i
			i += 1
		ans.append(isPrime.count(True))
	except EOFError:
		break
for num in ans:
	print num

### FIXED CODE ###

MAX = 1000000
prime = [1] * MAX
prime[0], prime[1] = 0, 0
i = 2
while i * i < MAX:
    j = 2
    while i * j < MAX:
        prime[i * j] = 0
        j += 1
    i += 1
for k in range(1, len(prime)):
    prime[k] += prime[k-1]

while True:
    try:
        n = int(raw_input())
        print prime[n]
    except EOFError:
        break
### BUGGY CODE ###

def cal_ans(x):
    ans = (x*(x+1)/2)/x
    return ans
n,k = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(cal_ans,p))

ans_temp = 0
ans_list = []
for i in range(n-k+1):
    if ans_temp < sum(p[i:i+k]):
            ans_temp = sum(p[i:i+k])
print(ans_temp)

### FIXED CODE ###

# import numpy as np

def cal_ans(x):
    ans = (x+1)/2
    return ans
n,k = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(cal_ans,p))

ans_temp = 0
ans_list = []
S = [0]
for i in range(n):
    S.append(S[i]+p[i])
# print(p)
# print(S)
# for i in range(n-k+1):
#     ans_list.append(sum(p[i:i+k]))
t_len = len(S)
ans1 = 0
for i in range(t_len - k):
    if ans1 < S[i+k]-S[i]:
        ans1 = S[i+k]-S[i]
print(ans1)
# ans = 0
# for i in range(k):
#     ans += (ans_list[i]*(ans_list[i]+1)/2)/ans_list[i]
#     # print((ans_list[i]*(ans_list[i]+1)/2))
# print(ans)
### BUGGY CODE ###

s=input()
t=input()

a=len(s)
b=len(t)

dp=[ [0 for _ in range(a+1)] for _ in range(b+1)]

for j in range(1,b+1):
    for i in range(1,a+1):
        if s[i-1]==t[j-1]:
            dp[j][i]= dp[j-1][i-1]+1
        else:
            dp[j][i]= max(dp[j-1][i],dp[j][i-1])

#print(dp)

ans=""
x=a
y=b
while dp[y][x]!=0:
    if dp[y][x]==dp[y-1][x]:
        y -=1
    elif dp[y][x]==dp[y][x-1]:
        x -=1
    else:
        ans += s[x-1]
        y -=1
        x -=1
print(ans[::-1])

### FIXED CODE ###

s=input()
t=input()

a=len(s)
b=len(t)

dp=[ [0 for _ in range(a+1)] for _ in range(b+1)]

for j in range(1,b+1):
    for i in range(1,a+1):
        if s[i-1]==t[j-1]:
            dp[j][i]= dp[j-1][i-1]+1
        else:
            dp[j][i]= max(dp[j-1][i],dp[j][i-1])

#print(dp)

ans=""
x=a
y=b
while dp[y][x]!=0:
    if dp[y][x]==dp[y-1][x]:
        y -=1
    elif dp[y][x]==dp[y][x-1]:
        x -=1
    else:
        ans += s[x-1]
        y -=1
        x -=1
print(ans[::-1])
### BUGGY CODE ###

S=input()
TL=len(S)
SL=list(S[i] for i in range(TL))#床の情報
BL=list(1 for i in range(TL))
CL=list(i for i in range(TL)) #子供の座標

for j in range(TL):
  i=j
  hozon=j
  if SL[i]=="R":
   
    while True:
      if SL[i]=="L":
        index=i
        #print(index)
        break
      i=i+1
    idou=index-hozon
    if idou%2==0:
      CL[hozon]=index
    else:
      CL[hozon]=index-1
  else:
  
    while True:
      if SL[i]=="R":
        index=i
        #print(index)
        break
      i=i-1
    idou=hozon-index
    if idou%2==0:
      CL[hozon]=index
    else:
      CL[hozon]=index+1
for i in range(TL):
  BL[i]=CL.count(i)
print(*BL)

### FIXED CODE ###

S=input()
TL=len(S)
SL=list(S[i] for i in range(TL))#床の情報
BL=[0]*TL
ans=[0]*TL #子供の座標
cnt=0
for j in range(2):
  for i in range(TL):
    
    if SL[i]=="R":
      cnt=cnt+1
    else:
      ans[i]=ans[i]+cnt//2
      ans[i-1]=ans[i-1]+(cnt+1)//2
      cnt=0
    
  SL.reverse()
  ans.reverse()
  for i in range(TL):
    if SL[i]=="R":
      SL[i]="L"
    else:
      SL[i]="R" 
for i in range(TL):
  print(ans[i])
### BUGGY CODE ###

def distance(i,j,x,y):
    return min(j-i,abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)


n,x,y=map(int,input().split())
for k in range(1,n):
    ans=0
    for i in range(1,n+1):
        for j in range(i,n+1):
            if distance(i,j,x,y)==k:
                ans+=1
    print(ans)

### FIXED CODE ###

def distance(i,j,x,y):
    return min(j-i,abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)


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

ans=[0]*n
for i in range(1,n+1):
    for j in range(i,n+1):
            ans[distance(i,j,x,y)-1]+=1
for i in range(n-1):
    print(ans[i])
### BUGGY CODE ###

h, n = map(int, input().split())
A, B = [], []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
F = [0]
for i in range(1, h+1):
    f = 1 << 30
    for a, b in zip(A, B):
        if i < a:
            f = min(f, b)
        else:
            f = min(f, F[i-a]+b)
    F.append(f)
print(f)


### FIXED CODE ###

inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = {}
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = {}
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    if a > 1:
        if a not in g_tmp:
            g_tmp[a] = 1
        else:
            g_tmp[a] += 1

    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    while tmp <= A[i] ** 0.5:
        cnt = 0
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            cnt += 1
        if cnt > 0:
            g[tmp] = max(g[tmp], cnt)
        tmp += 1
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

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

from fractions import Fraction
N = int(input())
A = []
for _ in range(N):
    A.append(Fraction(input()))
ans=0
for i in range(N):
    for j in range(i+1,N):
        if (A[i].numerator * A[j].numerator ) % (A[i].denominator * A[j].denominator) == 0 :
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
a = [[0 for j in range(19)] for i in range(19)]
ans=0
for _ in range(N):
    A=input()
    if A.find('.') > 0:
        count2 = 10 - len(A) + A.find('.')
        count5 = 10 - len(A) + A.find('.')
    else:
        count2 = 9
        count5 = 9
    tmp = int(A.replace('.', ''))
    while count2 < 18:
        if tmp % 2 == 0:
            count2 += 1
            tmp //= 2
        else:
            break
    while count5 < 18:
        if tmp % 5 == 0:
            count5 += 1
            tmp //= 5
        else:
            break
    for i in range(18-count2,19):
        for j in range(18-count5,19):
            ans += a[i][j]
    a[count2][count5] += 1
print(ans)
### BUGGY CODE ###

x = int(input())
c = []

for b in range(1,x+1):
  for q in range(2,x+2):
    a = b**q
    if a <=x:
      c.append(a)

C = set(c)
print(max(C))

### FIXED CODE ###

x = int(input())
c = 1

for b in range(1,x):
  for q in range(2,x):
    if b**q <=x:
      c = max(c,b**q)
    else:
      break
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
num = [0]*100000
s = sum(A)
for i in range(Q):
    B[i], C[i] = map(int,input().split())
for i in range(max(A)):
    num[i] = A.count(i+1)
for i in range(Q):
    if num[B[i]-1] == 0:
        print(s)
        continue
    else: 
        s += (C[i]-B[i])*num[B[i]-1]
        print(s)
        num[C[i]-1] += num[B[i]-1]
        num[B[i]-1] = 0

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0
### BUGGY CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]    
c = collections.Counter(ls)
count = c.most_common()[0][1]
ans = []
if c.most_common()[0][1] == 1:
    ls.sort()
    for i in ls:
        print(i)
else:
    for i in range(len(c)):
        p = c.most_common()
        if p[i][1] == count:
            ans.append(p[i][0])
        else:
            break   
    ans.sort()
    for i in ans:
      print(i)

### FIXED CODE ###

import collections
from collections import Counter

n = int(input())
ls = [input() for i in range(n)]    
c = Counter(ls).most_common()

count = c[0][1]
ans = []

for i in range(len(c)):
    if c[i][1] == count:
        ans.append(c[i][0])
    else:
        break   
ans = sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

from collections import Counter
N=int(input())
s=[0 for _ in range(N)]
count=0
for i in range(N):
    s[i]=input()
for t in range(N):
    for i in range(N):
        if Counter(s[i])==Counter(s[t]):
            count+=1
print(int((count-N)/2))

### FIXED CODE ###

N=int(input())
S=[''.join(sorted((input()))) for i in range(N)]
P={}
for i in range(N):
    if S[i] in P:
        P[S[i]]+=1
    else:
        P[S[i]]=0
for i in P.keys():
    if P[i]>=2:
        P[i]=P[i]*(P[i]+1)/2
print(int(sum(P.values())))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

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

for i in range(1, N):
  dp[i] = min([dp[i-j-1]+abs(h[i]-h[i-j-1]) for j in range(min(i,K))])

print(dp[N-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

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

for i in range(1, N):
  dp[i] = min([dp[i-j-1]+abs(h[i]-h[i-j-1]) for j in range(min(i,K))])

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

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

total = 0
for i in range(n):
    tmp = lis[i]
    flag = 1
    for j in range(i):
        if tmp > lis[j]:
            flag = 0
            break
    if flag:
        total += 1
        
print(total)

### FIXED CODE ###

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

total = 0
mini = lis[0]
for i in range(n):
    mini = min(mini, lis[i])
    if mini == lis[i]:
        total += 1
    
print(total)
### BUGGY CODE ###

s = input()
q = int(input())
flag = 0b0
for i in range(q) :
    t = input()
    if t == "1" :
        flag ^= 1
        continue
    t, f, c = t.split(" ")
    f = int(f)
    s = c*((flag+f)%2) + s + c*((flag+f+1)%2)
if flag == 0 :
    print(s)
else :
    print(s[::-1])

### FIXED CODE ###

right = input()
Q = int(input())
flag = 0b1
left = ""
for i in range(Q):
    q = input()
    if q == "1":
        flag ^= 1
        continue
    m,f,c = q.split(" ")
    f = int(f)
    left += c*(1-flag)*(f-1)
    right += c*flag*(f-1)
    left += c*flag*(2-f)
    right += c*(1-flag)*(2-f)
if flag == 1:
    print(left[::-1]+right)
else:
    print(right[::-1]+left)
### BUGGY CODE ###

_ = input()
s = list(map(int, input().split()))
n = int(input())
list_ = []
for _ in range(n):
  k,v = map(int, input().split())
  list_.append({k:v})

for maps in list_:
  k=list(maps.keys())[0]
  v=list(maps.values())[0]
  for i in range(len(s)): 
    if s[i]==k:
      s[i] = v
  ans = 0
  for num in s:
    ans += int(num)
  print(ans)



### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))
defo = sum(a)
default = [0]*100001
for i in a:
  default[i]+=1

q = int(input())
for _ in range(q):
  b, c = map(int, input().split())
  defo = defo + (c-b)*default[b]
  print(defo)
  default[c] += default[b]
  default[b] = 0
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

cc = []

for idx in range(N):
    if S[idx:idx + 2] == "AC":
        cc.append(1)
    else:
        cc.append(0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(sum(cc[l - 1:r]) - cc[r - 1])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

cc = []

acc = 0

for idx in range(N):
    if S[idx - 1:idx + 1] == "AC":
        acc = acc + 1
    cc.append(acc)

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

A,B,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = [0 for _ in range(m)]
y = [0 for _ in range(m)]
c = [0 for _ in range(m)]
for i in range(m):
    x[i],y[i],c[i] = map(int,input().split())

ans = 10000000000

for i in range(A):
    for j in range(B):
        for k in range(m):
            if(i+1 == x[k] and j+1 == y[k]):
                price = a[i] + b[j] - c[k]
            else:
                price = a[i] + b[j]
            ans = min(ans,price)
print(ans)

### FIXED CODE ###

A,B,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = [0 for _ in range(m)]
y = [0 for _ in range(m)]
c = [0 for _ in range(m)]
for i in range(m):
    x[i],y[i],c[i] = map(int,input().split())

ans = min(a)+min(b)

for i in range(m):
    ans = min(ans,(a[x[i]-1] + b[y[i]-1]) - c[i])
print(ans)
### BUGGY CODE ###

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

for _ in range(m):
    b,c = map(int, input().split())
    for _ in range(b):
        a.append(c)

a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

n,m = map(int, input().split())
a = sorted(list(map(int,input().split())))
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True )
count = 0
for b,c in bc:
    for _ in range(b):
        if count == n or a[count] >= c:
            break

        a[count] = c
        count += 1

print(sum(a))