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

city = []

count = 1

for i in range(M):

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

    city.append([p,y])

city_sorted = sorted(city)

for i in range(M):

    if city_sorted[i][0] == city_sorted[i-1][0] and i != 0:

        count += 1

    else:

        count = 1

    city_sorted[i][1] = count

for i in range(M):

    number_f = "0"*(6-len(str(city[i][0]))) + str(city[i][0])

    number_b = "0"*(6-len(str(city[i][1]))) + str(city[i][1])

    print((number_f + number_b))
N,M = list(map(int,input().split()))

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

info_new = sorted(info,key=lambda x:(x[0],x[1]))

note = info_new[0][0]

cnt = 1

for i in range(M):

    if info_new[i][0] == note:

        info_new[i][1] = cnt

        cnt += 1

    else:

        note = info_new[i][0]

        cnt = 1

        info_new[i][1] = cnt

        cnt += 1

        

for i in range(M):

    pri = str(info[i][0])

    bir = str(info[i][1])

    number = "0"*(6-len(pri)) + pri + "0"*(6-len(bir)) + bir

    print(number)
N, M = list(map(int, input().split()))
city = []
count = 1
for i in range(M):
    p, y = list(map(int, input().split()))
    city.append([p, y])
city_sorted = sorted(city)
for i in range(M):
    if city_sorted[i][0] == city_sorted[i - 1][0] and i != 0:
        count += 1
    else:
        count = 1
    city_sorted[i][1] = count
for i in range(M):
    number_f = "0" * (6 - len(str(city[i][0]))) + str(city[i][0])
    number_b = "0" * (6 - len(str(city[i][1]))) + str(city[i][1])
    print((number_f + number_b))

N, M = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(M)]
info_new = sorted(info, key=lambda x: (x[0], x[1]))
note = info_new[0][0]
cnt = 1
for i in range(M):
    if info_new[i][0] == note:
        info_new[i][1] = cnt
        cnt += 1
    else:
        note = info_new[i][0]
        cnt = 1
        info_new[i][1] = cnt
        cnt += 1
for i in range(M):
    pri = str(info[i][0])
    bir = str(info[i][1])
    number = "0" * (6 - len(pri)) + pri + "0" * (6 - len(bir)) + bir
    print(number)

-city = [] -count = 1 +info = [list(map(int, input().split())) for i in range(M)] +info_new = sorted(info, key=lambda x: (x[0], x[1])) +note = info_new[0][0] +cnt = 1 -    p, y = list(map(int, input().split())) -    city.append([p, y]) -city_sorted = sorted(city) +    if info_new[i][0] == note: +        info_new[i][1] = cnt +        cnt += 1 +    else: +        note = info_new[i][0] +        cnt = 1 +        info_new[i][1] = cnt +        cnt += 1 -    if city_sorted[i][0] == city_sorted[i - 1][0] and i != 0: -        count += 1 -    else: -        count = 1 -    city_sorted[i][1] = count -for i in range(M): -    number_f = "0" * (6 - len(str(city[i][0]))) + str(city[i][0]) -    number_b = "0" * (6 - len(str(city[i][1]))) + str(city[i][1]) -    print((number_f + number_b)) +    pri = str(info[i][0]) +    bir = str(info[i][1]) +    number = "0" * (6 - len(pri)) + pri + "0" * (6 - len(bir)) + bir +    print(number)