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

L = []

ans = []

for i in range(M) :

    L.append(list(map(int,input().split())))

    ans.append([])



C = []

for i in range(N+1) :

    C.append([])



for i, (p,y) in enumerate(L) :

    C[p].append([y,i])



for p in range(N+1) :

    for i,(y,_) in enumerate(sorted(C[p])) :

        ans[_] = str(p).zfill(6) + str(i+1).zfill(6)

for i in range(M) :

    print((ans[i]))

from bisect import *



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

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

D = {}

for i in range(M) :

    p, y = L[i]

    if p not in D :

        D[p] = [y]

    else :

        D[p].append(y)



for p in D :

    D[p] = sorted(D[p])



for i in range(M) :

    p, y = L[i]

    ind = bisect_left(D[p], y)

    res = str(p).zfill(6) + str(ind+1).zfill(6)

    print(res)

N, M = list(map(int, input().split()))
L = []
ans = []
for i in range(M):
    L.append(list(map(int, input().split())))
    ans.append([])
C = []
for i in range(N + 1):
    C.append([])
for i, (p, y) in enumerate(L):
    C[p].append([y, i])
for p in range(N + 1):
    for i, (y, _) in enumerate(sorted(C[p])):
        ans[_] = str(p).zfill(6) + str(i + 1).zfill(6)
for i in range(M):
    print((ans[i]))

from bisect import *

N, M = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(M)]
D = {}
for i in range(M):
    p, y = L[i]
    if p not in D:
        D[p] = [y]
    else:
        D[p].append(y)
for p in D:
    D[p] = sorted(D[p])
for i in range(M):
    p, y = L[i]
    ind = bisect_left(D[p], y)
    res = str(p).zfill(6) + str(ind + 1).zfill(6)
    print(res)

+from bisect import * + -L = [] -ans = [] +L = [list(map(int, input().split())) for i in range(M)] +D = {} -    L.append(list(map(int, input().split()))) -    ans.append([]) -C = [] -for i in range(N + 1): -    C.append([]) -for i, (p, y) in enumerate(L): -    C[p].append([y, i]) -for p in range(N + 1): -    for i, (y, _) in enumerate(sorted(C[p])): -        ans[_] = str(p).zfill(6) + str(i + 1).zfill(6) +    p, y = L[i] +    if p not in D: +        D[p] = [y] +    else: +        D[p].append(y) +for p in D: +    D[p] = sorted(D[p]) -    print((ans[i])) +    p, y = L[i] +    ind = bisect_left(D[p], y) +    res = str(p).zfill(6) + str(ind + 1).zfill(6) +    print(res)