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

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(reverse=True)
inf=1000000000
ma=ab[0][0]
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=ab[i]
    for j in range(h):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                if j+x[0]>=h:
                    dp[h]=min(dp[h],dp[j]+x[1])
                else:
                    dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(dp[h])


### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(reverse=True)
inf=1000000000
ma=ab[0][0]
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=ab[i]
    for j in range(h):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                if j+x[0]>=h:
                    dp[h]=min(dp[h],dp[j]+x[1])
                else:
                    dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(dp[h])
### BUGGY CODE ###

n, m = map(int, input().split())
cards = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

c = []
flag = 0
for i in bc:
    for j in range(i[0]):
        c.append(i[1])
        
cards += c
cards.sort(reverse = True)
    
print(sum(cards[:n]))

### FIXED CODE ###

n, m = map(int, input().split())
cards = [[1, int(i)] for i in input().split()]
bc = [list(map(int, input().split())) for _ in range(m)]
cards += bc
cards.sort(key = lambda x: x[1], reverse = True)

l = []
flag = 0
for i in cards:
    for j in range(i[0]):
        l.append(i[1])
        if len(l) == n:
            flag = 1
            break
    if flag:
        break

print(sum(l))
### BUGGY CODE ###

from collections import defaultdict

H, W, m = map(int, input().split())

hor = defaultdict(int)
ver = defaultdict(int)
f = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[h - 1][w - 1] = 1

hor = sorted(hor.items(), key=lambda x:-x[1])
ver = sorted(ver.items(), key=lambda x:-x[1])

ans = hor[0][1] + ver[0][1]
i = 0
while i < len(hor) and hor[i][1] == hor[0][1]:
    j = 0
    while j < len(ver) and ver[j][1] == ver[0][1]:
        if f[hor[i][0]][ver[j][0]] == 0:
            print(ans)
            exit()
        j += 1
    i += 1
print(ans - 1)


### FIXED CODE ###

import sys
from collections import defaultdict

input = sys.stdin.readline

H, W, m = map(int, input().split())

hor = [0] * H
ver = [0] * W
f = defaultdict(int)
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[str(h - 1) + '|' + str(w - 1)] = 1

hmax = max(hor)
hs = [i for i, v in enumerate(hor) if v == hmax]
vmax = max(ver)
vs = [i for i, v in enumerate(ver) if v == vmax]


ans = hmax + vmax

if len(hs) * len(vs) > m:
    print(ans)
    exit()

for k1 in hs:
    for k2 in vs:
        if f[str(k1) + '|' + str(k2)] == 0:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_c

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

ans_list = []

for i in range(1, N + 1):
    ans_list.append(str(A_list.index(i) + 1))

print(' '.join(ans_list))

### FIXED CODE ###

# https://atcoder.jp/contests/abc142/tasks/abc142_c

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

# ans = str(A_list.index(1) + 1)
# for i in range(2, N + 1):
#     tmp = str(A_list.index(i) + 1)
#     ans = ' '.join([ans, tmp])



ans_list = [0] * N

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

# リストを空白区切りで出力
print(*ans_list)
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(n):
    ans += i

print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import math
num=int(input())
target=list(map(int, input().split()))

def comb(N, r):
    return math.factorial(N) // (math.factorial(N - r) * math.factorial(r))

for i in range(num):
    A=target.copy()
    A.pop(i)
    out=0
    for j in set(A):
        if A.count(j)>1:
            base = comb(A.count(j),2)
            out=out+base
    print(out)

### FIXED CODE ###

import collections
n = int(input())
arr = list(map(int, input().split()))
cnt = collections.Counter(arr)
total = 0
for i in cnt.keys():
  patern = cnt[i]*(cnt[i]-1)//2
  total += patern
for j in range(n):
  tmp = total
  total -= cnt[arr[j]]*(cnt[arr[j]]-1)//2
  total += (cnt[arr[j]]-1)*(cnt[arr[j]]-2)//2
  print(total)
  total = tmp
### BUGGY CODE ###

import math

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

n = int(input())
# k,x = map(int,input().split())
s_l = []
for i in range(n):
        s_l.append(input())

for i in range(n):
        a = ''
        for x in sorted(s_l[i]):
                a += x
        s_l[i] = a

cnt = 0
# for i in range(n):
#         for j in range(1,n-i):
#                 if s_l[i] == s_l[i+j]:
#                         cnt += 1
set_s_l = set(s_l)
if len(s_l) == len(set_s_l):
        print(0)
else:
        l = []
        for val in set_s_l:
                l.append(s_l.count(val))
        for i in l:
                if i > 1:
                        if i == 2:
                                cnt += 1
                        elif i == 3:
                                cnt +=i
                        else:
                                cnt += c(i,2)
        print(cnt)


# 0 1 2 3 4
#     2

### FIXED CODE ###

import math
from collections import defaultdict

n = int(input())
# k,x = map(int,input().split())
s_l = []
for i in range(n):
        s = list(input())
        s.sort()
        s_l.append(''.join(s))

# for i in range(n):
#         s_l.append(''.join(sorted(s_i_l[i])))
#         # for x in sorted(s_l[i]):
#         #         a += x
#         # s_l[i] = a
cnt = 0

d = defaultdict(lambda: 0)
for s in s_l:
        d[s] += 1

for v in d.values():
        cnt += int(v*(v-1)/2)
print(cnt)
### BUGGY CODE ###

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

M = 10**9 + 7


def my_pow(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return my_pow(x ** 2, n // 2) % M
    else:
        return x * my_pow(x ** 2, (n - 1) // 2) % M

    
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

all_pattern = my_pow(2, n)
dislike = cmb(n, a) + cmb(n, b)
dislike = dislike % M


print( (all_pattern - dislike - 1) )


### FIXED CODE ###

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

M = 10 ** 9 + 7

all = pow(2, n, M) - 1
all %= M

def C(n,x):
    num = 1
    den = 1
    for i in range(x):
        num *= (n-i)
        num %= M
        den *= (i+1)
        den %= M

    inv = pow(den, M-2, M)

    return num * inv % M

ans = all - C(n,a) - C(n,b)
ans %= M
print(ans)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    city = [[] for i in range(n)]
    for p, y in py:
        city[p-1].append(y)
        city[p-1].sort()
    for p, y in py:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(bisect.bisect_left(city[p-1],y) + 1)
        b = b[-6:]
        print(a+b)    
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()
### BUGGY CODE ###

q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        num=int(i**0.5)
        like_num=(i+1)//2
        if like_num==1:continue
        num2=int(like_num**0.5)
        for j in range(3,num+1,2):
            if i%j==0:break
        else:
            for j in range(2,num2+1):
                if like_num!=2 and like_num%j==0:break
            else:
                cnt+=1
                #print(i,cnt)
    print(cnt)

### FIXED CODE ###

q=int(input())
l=[list(map(int,input().split())) for i in range(q)]

def jud(i):
    #iの素数判定
    num=int(i**0.5)+1
    for k in range(2,num):
        if i%k==0:
            return 0
    return 1

s=[0]*(10**5+1)
for i in range(2,10**5+1):
    if i%2==0:
        s[i]=s[i-1]
    else:
        if jud(i)*jud((i+1)//2)==1:
            s[i]=s[i-1]+1
        else:
            s[i]=s[i-1]

for k,v in l:
    ans=s[v]-s[k-1]
    print(ans)
### BUGGY CODE ###

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

flag = True

for b in a:
    if a.count(b) >= 2:
        flag = False
        break


if flag:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

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

if len(set(a)) == n:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

H,W,D = list(map(int, input().split()))
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
L = [0 for _ in range(Q)]
R = [0 for _ in range(Q)]
for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))


masu = [[0,0] for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        masu[A[i][j]-1] = [i, j]

MP = [0 for _ in range(Q)]
for k in range(Q):
    XY = masu[L[k]-1:R[k]:D]
    for i in range(len(XY)-1):
        MP[k] += abs(XY[i][0]-XY[i+1][0])
        MP[k] += abs(XY[i][1]-XY[i+1][1])


for i in range(Q):
    print(MP[i])

### FIXED CODE ###

H,W,D = list(map(int, input().split()))
A = []
for i in range(H):
    A.append(list(map(int, input().split())))

Q = int(input())
L = [0 for _ in range(Q)]
R = [0 for _ in range(Q)]
for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

masu = [[0,0] for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        masu[A[i][j]-1] = [i, j]

MP = [0 for _ in range(H*W)]
for i in range(H*W):
    if i < D:
        MP[i] = 0
    else:
        MP[i] = MP[i-D] + abs(masu[i][0]-masu[i-D][0]) + abs(masu[i][1]-masu[i-D][1])

for i in range(Q):
    print(MP[R[i]-1] - MP[L[i]-1])
### 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[i])
### BUGGY CODE ###

# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s

#main
n=int(input())
#A,B,C=map(int,input().split())
S=[]
C={}
for a in range(n):
    s=readline()
    if not s in C:
        C[s]=1
    else:
        C[s]+=1
A=[]
for a,b in C.items():
    A.append([b,a])
A.sort(key=lambda x:(-x[0],x[1]))
max_=A[0][0]
for a in A:
    if(a[0]!=max_):break
    print(a[1])
    
 
 





### FIXED CODE ###

n=int(input())
#A,B,C=map(int,input().split())
S=[]
C={}
for a in range(n):
    s=input()
    if not s in C:
        C[s]=1
    else:
        C[s]+=1
A=[]
for a,b in C.items():
    A.append([b,a])
A.sort(key=lambda x:(-x[0],x[1]))
max_=A[0][0]
for a in A:
    if(a[0]!=max_):break
    print(a[1])
### BUGGY CODE ###

N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    for j in range(N):
        if B[j] and j != i:
            if A[j]==A[i]:
                B[i] = False
                B[j] = False
            elif A[j]%A[i]==0:
                B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max

for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        for j in range(2,a_Max+1):
            if a*j > a_Max:
                break
            B[a*j-1] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
            
ans = 0
for b in B:
    if b == 1:
        ans += 1

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

# https://img.atcoder.jp/abc123/editorial.pdf 解法 #1 - 工夫したソートで O(K^2 log K)

import functools
import operator
import itertools

def solve(X, Y, Z, K, A, B, C):
    AB = [functools.reduce(operator.add, x) for x in itertools.product(A, B)]
    AB.sort(reverse=True)
    AB = AB[:K]
    ABC = [functools.reduce(operator.add, x) for x in itertools.product(AB, C)]
    ABC.sort(reverse=True)
    ABC = ABC[:K]
    print("\n".join(map(str, ABC)))

if __name__ == "__main__":
    X, Y, Z, K = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())), reverse=True)
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())), reverse=True)
    solve(X, Y, Z, K, A, B, C)

### FIXED CODE ###

from collections import defaultdict

def append(m, printed, cand_a, cand_b, cand_c):
    key = "{}-{}-{}".format(cand_a, cand_b, cand_c)
    key2 = "{}-{}-{}".format(cand_a-1, cand_b, cand_c)
    key3 = "{}-{}-{}".format(cand_a, cand_b-1, cand_c)
    key4 = "{}-{}-{}".format(cand_a, cand_b, cand_c-1)
    if not key in printed \
            and cand_a < len(A) \
            and cand_b < len(B) \
            and cand_c < len(C) \
            and not key in m \
            and not key2 in m \
            and not key3 in m \
            and not key4 in m :
#       print("Appended {}".format(key))
        m[key] = A[cand_a] + B[cand_b] + C[cand_c]
    return m

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

a = 0
b = 0
c = 0

n_print = 0
#print(A, B, C)
memo = {}
printed = defaultdict(lambda: False)
while True:
    summ = A[a] + B[b] + C[c]
    printed["{}-{}-{}".format(a, b, c)] = True

    print(summ)

#   print(memo.items())
#   print(a, b, c)
#   print("")

    n_print += 1
    if n_print == K:
        break

    memo = append(memo, printed, a+1, b, c)
    memo = append(memo, printed, a, b+1, c)
    memo = append(memo, printed, a, b, c+1)

    max_k = max(memo, key=memo.get)
    a, b, c = max_k.split("-")
    a = int(a)
    b = int(b)
    c = int(c)
        
    memo.pop(max_k)
#   print("Pop {}".format(max_k))
### BUGGY CODE ###

N, A, B = map(int, input().split())
if A == 0:
    print('0')
elif B == 0:
    print(N)
else:
    result = 0
    while N > A:
        N -= A
        result += A
        N -= B
    if N > 0:
        print(result + N)
    else:
        print(result)

### FIXED CODE ###

N, A, B = map(int, input().split())
if A == 0:
    print('0')
elif B == 0:
    print(N)
else:
    tmp = N // (A + B)
    result = tmp * A
    N -= tmp * (A + B)
    if N > A:
        result += A
    else:
        result += N
    print(result)
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for i in range(m):
  b,c = map(int,input().split())
  for j in range(b):
    if c>A[j]:
      A[j] = c
  A.sort()
print(sum(A))

### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
CntA = [1 for i in range(n)]
for i in range(m):
  b,c = map(int,input().split())
  A.append(c)
  CntA.append(b)
Z = list(zip(A,CntA))
Z.sort(reverse=True)
ans = 0
for z in Z:
  if n>z[1]:
    ans+=z[1]*z[0]
    n-=z[1]
  else:
    ans+=n*z[0]
    break
print(ans)
### BUGGY CODE ###

H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import scipy as sp
import scipy.ndimage as ni
A = sp.array(A, dtype= sp.int8)
WKU = sp.zeros(A.shape, dtype=sp.int8)
WKD = sp.zeros(A.shape, dtype=sp.int8)
WKL = sp.zeros(A.shape, dtype=sp.int8)
WKR = sp.zeros(A.shape, dtype=sp.int8)
i = 0
S = H * W
while True:
    if sp.sum(A) == S:
        break
    WK = 0 + A
    ni.shift(A, (0, 1), WKR)
    ni.shift(A, (0, -1), WKL)
    ni.shift(A, (1, 0), WKU)
    ni.shift(A, (-1, 0), WKD)
    A |= WKR | WKL | WKU | WKD
    i += 1

print(i)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
P = [K for i in range(N)]


for ans in A:
    for index in range(N):
        if (ans-1)==index:
            continue
        P[index]-=1

for value in P:
    if value<=0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
P = [K-Q]*N


for i in range(Q):
    P[A[i]-1]+=1

for value in P:
    if value<=0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math
N = int(input())
S = list(input())

count = 0
while True:
    if "".join(S[:2]) == "#.":
        S[0] = "."
        count += 1
    if "".join(S[-2:]) == "#.":
        S[-1] = "#"
        count += 1
    S = S[2:-2]
    if not S:
        break
        
print(count)

### FIXED CODE ###

N = int(input())
S = input()

white_count = S.count(".")
black_count = 0
ans = white_count
for s in S:
    if s == "#":
        black_count += 1
    else:
        white_count -= 1
    if ans > black_count + white_count:
        ans = black_count + white_count

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

s = input()
t = s.replace("LR","L,R")
# print(t)
u = t.split(",")
# print(u)
ans = []
for i in range(len(u)):
    # print(u[i])
    j = u[i].find("RL")
    # print(j)
    numR = j+1
    numL = len(u[i])-(j+1)
    a = [0]*len(u[i])
    a[j] = (numR+1)//2 + (numL)//2
    a[j+1] = (numR)//2 + (numL+1)//2
    ans = ans + a
print(" ".join(list(map(str, ans))))

### FIXED CODE ###

s = input()
l = len(s)
ans = [0]*l
count = 0
for i in range(l):
    if s[i]=="R" and s[i+1]=="R":
        count += 1
    elif s[i]=="R" and s[i+1]=="L":
        count += 1
        ans[i] += (count+1)//2
        ans[i+1] += count//2
        count = 0
for i in reversed(range(l)):
    # print(i)
    # print(s[i])
    if s[i]=="L" and s[i-1]=="L":
        count += 1
    elif s[i]=="L" and s[i-1]=="R":
        count += 1
        ans[i] += (count+1)//2
        ans[i-1] += count//2
        count = 0
print(" ".join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    bi, ci = map(int, input().split())
    b.append(bi)
    c.append(ci)

for i in range(q):
    a = [(c[i] if j == b[i] else j) for j in a]
    print(sum(a))


### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    bi, ci = map(int, input().split())
    b.append(bi)
    c.append(ci)

count = collections.Counter(a)
sums = sum(a)

for i in range(q):
    sums += count[b[i]] * (c[i] - b[i])
    print(sums)
    count[c[i]] += count[b[i]]
    count[b[i]] = 0