from collections import defaultdict 

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

py = []

for i in range(m):

    p,y = list(map(int,input().split()))

    py.append([p,y])

spy = sorted(py,key=lambda x:x[1])



cnt = [0]*n

id =  defaultdict(int)

for i in spy:

    p,y = i

    cnt[p-1] += 1

    id[(p,y)] = str(p).zfill(6)+str(cnt[p-1]).zfill(6)



for i in py:

    p,y = i

    print((id[(p,y)]))
n,m = list(map(int,input().split()))

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

c = [0]*n

sort_py = sorted(py,key=lambda x:x[1])

ans = dict()

for p,y in sort_py:

    c[p-1] += 1

    ans[p,y] = str(p).zfill(6)+str(c[p-1]).zfill(6)



for p,y in py:

    print((ans[p,y]))
from collections import defaultdict

n, m = list(map(int, input().split()))
py = []
for i in range(m):
    p, y = list(map(int, input().split()))
    py.append([p, y])
spy = sorted(py, key=lambda x: x[1])
cnt = [0] * n
id = defaultdict(int)
for i in spy:
    p, y = i
    cnt[p - 1] += 1
    id[(p, y)] = str(p).zfill(6) + str(cnt[p - 1]).zfill(6)
for i in py:
    p, y = i
    print((id[(p, y)]))

n, m = list(map(int, input().split()))
py = [list(map(int, input().split())) for i in range(m)]
c = [0] * n
sort_py = sorted(py, key=lambda x: x[1])
ans = dict()
for p, y in sort_py:
    c[p - 1] += 1
    ans[p, y] = str(p).zfill(6) + str(c[p - 1]).zfill(6)
for p, y in py:
    print((ans[p, y]))

-from collections import defaultdict - -py = [] -for i in range(m): -    p, y = list(map(int, input().split())) -    py.append([p, y]) -spy = sorted(py, key=lambda x: x[1]) -cnt = [0] * n -id = defaultdict(int) -for i in spy: -    p, y = i -    cnt[p - 1] += 1 -    id[(p, y)] = str(p).zfill(6) + str(cnt[p - 1]).zfill(6) -for i in py: -    p, y = i -    print((id[(p, y)])) +py = [list(map(int, input().split())) for i in range(m)] +c = [0] * n +sort_py = sorted(py, key=lambda x: x[1]) +ans = dict() +for p, y in sort_py: +    c[p - 1] += 1 +    ans[p, y] = str(p).zfill(6) + str(c[p - 1]).zfill(6) +for p, y in py: +    print((ans[p, y]))