from operator import itemgetter



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

PY=[]

P=[[] for i in range(N)]

ans=[0 for i in range(M)]

for i in range(M):

    PYi=list(map(int,input().split()))

    PY.append(PYi)

    P[PYi[0]-1].append([i,PYi[1]])



for i in range(N):

    P[i]=sorted(P[i], key=itemgetter(1))



for i in range(N):

    for j in range(len(P[i])):

        ans[P[i][j][0]]=j+1



for i in range(M):

    a=format(PY[i][0],'06d')

    b=format(ans[i],'06d')

    print((a+b))
from operator import itemgetter



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

PY=[]

ans=[0 for i in range(M)]

cc=[0 for i in range(N)]

for i in range(M):

    PYi=list(map(int,input().split()))

    PY.append([i,PYi[0],PYi[1]])

     

PY=sorted(PY, key=itemgetter(2))



for i in range(M):

    cc[PY[i][1]-1]+=1

    ans[PY[i][0]]=format(PY[i][1],'06d')+format(cc[PY[i][1]-1],'06d')



for i in range(M):

    print((ans[i]))
from operator import itemgetter

N, M = list(map(int, input().split()))
PY = []
P = [[] for i in range(N)]
ans = [0 for i in range(M)]
for i in range(M):
    PYi = list(map(int, input().split()))
    PY.append(PYi)
    P[PYi[0] - 1].append([i, PYi[1]])
for i in range(N):
    P[i] = sorted(P[i], key=itemgetter(1))
for i in range(N):
    for j in range(len(P[i])):
        ans[P[i][j][0]] = j + 1
for i in range(M):
    a = format(PY[i][0], "06d")
    b = format(ans[i], "06d")
    print((a + b))

from operator import itemgetter

N, M = list(map(int, input().split()))
PY = []
ans = [0 for i in range(M)]
cc = [0 for i in range(N)]
for i in range(M):
    PYi = list(map(int, input().split()))
    PY.append([i, PYi[0], PYi[1]])
PY = sorted(PY, key=itemgetter(2))
for i in range(M):
    cc[PY[i][1] - 1] += 1
    ans[PY[i][0]] = format(PY[i][1], "06d") + format(cc[PY[i][1] - 1], "06d")
for i in range(M):
    print((ans[i]))

-P = [[] for i in range(N)] +cc = [0 for i in range(N)] -    PY.append(PYi) -    P[PYi[0] - 1].append([i, PYi[1]]) -for i in range(N): -    P[i] = sorted(P[i], key=itemgetter(1)) -for i in range(N): -    for j in range(len(P[i])): -        ans[P[i][j][0]] = j + 1 +    PY.append([i, PYi[0], PYi[1]]) +PY = sorted(PY, key=itemgetter(2)) -    a = format(PY[i][0], "06d") -    b = format(ans[i], "06d") -    print((a + b)) +    cc[PY[i][1] - 1] += 1 +    ans[PY[i][0]] = format(PY[i][1], "06d") + format(cc[PY[i][1] - 1], "06d") +for i in range(M): +    print((ans[i]))