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

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



PY.sort()



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



x = 1

P = PY[0][0]

for i in range(M):

    if P != PY[i][0]:

        x = 1

        P = PY[i][0]



    ans[PY[i][2]] = (P,x)

    x += 1



for p,x in ans:

    print((str(p).zfill(6) + str(x).zfill(6)))

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

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



PY.sort()



pnow = PY[0][0]

c = 1



ans = [-1 for i in range(M)]



for i in range(M):

    if pnow != PY[i][0]:

        c = 1

        pnow = PY[i][0]

    ans[PY[i][2]] = str(PY[i][0]).zfill(6) + str(c).zfill(6)

    c += 1



print(('\n'.join(ans)))

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort()
ans = [None for i in range(M)]
x = 1
P = PY[0][0]
for i in range(M):
    if P != PY[i][0]:
        x = 1
        P = PY[i][0]
    ans[PY[i][2]] = (P, x)
    x += 1
for p, x in ans:
    print((str(p).zfill(6) + str(x).zfill(6)))

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort()
pnow = PY[0][0]
c = 1
ans = [-1 for i in range(M)]
for i in range(M):
    if pnow != PY[i][0]:
        c = 1
        pnow = PY[i][0]
    ans[PY[i][2]] = str(PY[i][0]).zfill(6) + str(c).zfill(6)
    c += 1
print(("\n".join(ans)))

-ans = [None for i in range(M)] -x = 1 -P = PY[0][0] +pnow = PY[0][0] +c = 1 +ans = [-1 for i in range(M)] -    if P != PY[i][0]: -        x = 1 -        P = PY[i][0] -    ans[PY[i][2]] = (P, x) -    x += 1 -for p, x in ans: -    print((str(p).zfill(6) + str(x).zfill(6))) +    if pnow != PY[i][0]: +        c = 1 +        pnow = PY[i][0] +    ans[PY[i][2]] = str(PY[i][0]).zfill(6) + str(c).zfill(6) +    c += 1 +print(("\n".join(ans)))