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

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

A = [0 for k in range(M)]



for k in range(M):

    s, t = list(map(int,input().split()))

    P[s-1].append([t,k])



for k in range(N):

    P[k].sort()

    for l in range(len(P[k])):

        A[P[k][l][1]] = str(k+1).zfill(6) + str(l+1).zfill(6)



for a in A:

    print(("".join(a)))
N, M = list(map(int,input().split()))

C = [[] for k in range(N)]

for k in range(M):

    P, Y = list(map(int,input().split()))

    C[P-1].append([Y,k])

D = []

for e in C:

    D.append(sorted(e))

A = [0]*M

for k in range(N):

    c = 1

    for e in D[k]:

        A[e[1]] = (k+1)*1000000 + c

        c += 1

for e in A:

    print((str(e).zfill(12)))

N, M = list(map(int, input().split()))
P = [[] for k in range(N)]
A = [0 for k in range(M)]
for k in range(M):
    s, t = list(map(int, input().split()))
    P[s - 1].append([t, k])
for k in range(N):
    P[k].sort()
    for l in range(len(P[k])):
        A[P[k][l][1]] = str(k + 1).zfill(6) + str(l + 1).zfill(6)
for a in A:
    print(("".join(a)))

N, M = list(map(int, input().split()))
C = [[] for k in range(N)]
for k in range(M):
    P, Y = list(map(int, input().split()))
    C[P - 1].append([Y, k])
D = []
for e in C:
    D.append(sorted(e))
A = [0] * M
for k in range(N):
    c = 1
    for e in D[k]:
        A[e[1]] = (k + 1) * 1000000 + c
        c += 1
for e in A:
    print((str(e).zfill(12)))

-P = [[] for k in range(N)] -A = [0 for k in range(M)] +C = [[] for k in range(N)] -    s, t = list(map(int, input().split())) -    P[s - 1].append([t, k]) +    P, Y = list(map(int, input().split())) +    C[P - 1].append([Y, k]) +D = [] +for e in C: +    D.append(sorted(e)) +A = [0] * M -    P[k].sort() -    for l in range(len(P[k])): -        A[P[k][l][1]] = str(k + 1).zfill(6) + str(l + 1).zfill(6) -for a in A: -    print(("".join(a))) +    c = 1 +    for e in D[k]: +        A[e[1]] = (k + 1) * 1000000 + c +        c += 1 +for e in A: +    print((str(e).zfill(12)))