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

G = {}

for i in range(M):

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

    if P not in G:

        G[P]=[]

    G[P].append((i+1,Y))

C = []

for P in G:

    G[P] = sorted(G[P],key=lambda x:x[1])

    a = len(str(P))

    x = "0"*(6-a)+str(P)

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

        b = len(str(i+1))

        y = x+"0"*(6-b)+str(i+1)

        C.append((G[P][i][0],y))

C = sorted(C,key=lambda x:x[0])

for c in C:

    print((c[1]))
from bisect import bisect_left

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

C = {i:[] for i in range(1,N+1)}

city = [0 for _ in range(M+1)]

for j in range(1,M+1):

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

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

    city[j]=(p,y)

for p in C:

    if len(C[p])>0:

        C[p] = sorted(C[p],key=lambda x:x[0])

for j in range(1,M+1):

    p,y = city[j]

    ind = bisect_left(C[p],(y,j))

    p = str(p)

    if len(p)<6:

        p ="0"*(6-len(p))+p

    x = str(ind+1)

    if len(x)<6:

        x = "0"*(6-len(x))+x

    print((p+x))
N, M = list(map(int, input().split()))
G = {}
for i in range(M):
    P, Y = list(map(int, input().split()))
    if P not in G:
        G[P] = []
    G[P].append((i + 1, Y))
C = []
for P in G:
    G[P] = sorted(G[P], key=lambda x: x[1])
    a = len(str(P))
    x = "0" * (6 - a) + str(P)
    for i in range(len(G[P])):
        b = len(str(i + 1))
        y = x + "0" * (6 - b) + str(i + 1)
        C.append((G[P][i][0], y))
C = sorted(C, key=lambda x: x[0])
for c in C:
    print((c[1]))

from bisect import bisect_left

N, M = list(map(int, input().split()))
C = {i: [] for i in range(1, N + 1)}
city = [0 for _ in range(M + 1)]
for j in range(1, M + 1):
    p, y = list(map(int, input().split()))
    C[p].append((y, j))
    city[j] = (p, y)
for p in C:
    if len(C[p]) > 0:
        C[p] = sorted(C[p], key=lambda x: x[0])
for j in range(1, M + 1):
    p, y = city[j]
    ind = bisect_left(C[p], (y, j))
    p = str(p)
    if len(p) < 6:
        p = "0" * (6 - len(p)) + p
    x = str(ind + 1)
    if len(x) < 6:
        x = "0" * (6 - len(x)) + x
    print((p + x))

+from bisect import bisect_left + -G = {} -for i in range(M): -    P, Y = list(map(int, input().split())) -    if P not in G: -        G[P] = [] -    G[P].append((i + 1, Y)) -C = [] -for P in G: -    G[P] = sorted(G[P], key=lambda x: x[1]) -    a = len(str(P)) -    x = "0" * (6 - a) + str(P) -    for i in range(len(G[P])): -        b = len(str(i + 1)) -        y = x + "0" * (6 - b) + str(i + 1) -        C.append((G[P][i][0], y)) -C = sorted(C, key=lambda x: x[0]) -for c in C: -    print((c[1])) +C = {i: [] for i in range(1, N + 1)} +city = [0 for _ in range(M + 1)] +for j in range(1, M + 1): +    p, y = list(map(int, input().split())) +    C[p].append((y, j)) +    city[j] = (p, y) +for p in C: +    if len(C[p]) > 0: +        C[p] = sorted(C[p], key=lambda x: x[0]) +for j in range(1, M + 1): +    p, y = city[j] +    ind = bisect_left(C[p], (y, j)) +    p = str(p) +    if len(p) < 6: +        p = "0" * (6 - len(p)) + p +    x = str(ind + 1) +    if len(x) < 6: +        x = "0" * (6 - len(x)) + x +    print((p + x))