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

array = []

ans = []

for i in range(M):

    array.append(list(map(int, input().split()))+[i])

array.sort()

count = 1

for i in range(M):

    id_left = str(array[i][0])

    while len(id_left) < 6:

        id_left = '0' + id_left

    id_right = str(count)

    while len(id_right) < 6:

        id_right = '0' + id_right

    id = id_left + id_right

    ans.append([array[i][2],id])

    if i == M-1:

        break

    if array[i][0] != array[i+1][0]:

        count = 1

    else:

        count += 1

ans.sort()

for i in ans:

    print((i[1]))
N, M = list(map(int, input().split()))

p = []

for i in range(M):

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

    tmp.append(i)

    p.append(tmp)

p.sort()

ans = []

count = 1

for i in range(M):

    if p[i-1][0] != p[i][0]:

        count = 1

    elif i != 0:

        count += 1

    id = str(p[i][0]).zfill(6)+str(count).zfill(6)

    ans.append((p[i][2],id))

ans.sort()

for i in ans:

    print((i[1]))
N, M = list(map(int, input().split()))
array = []
ans = []
for i in range(M):
    array.append(list(map(int, input().split())) + [i])
array.sort()
count = 1
for i in range(M):
    id_left = str(array[i][0])
    while len(id_left) < 6:
        id_left = "0" + id_left
    id_right = str(count)
    while len(id_right) < 6:
        id_right = "0" + id_right
    id = id_left + id_right
    ans.append([array[i][2], id])
    if i == M - 1:
        break
    if array[i][0] != array[i + 1][0]:
        count = 1
    else:
        count += 1
ans.sort()
for i in ans:
    print((i[1]))

N, M = list(map(int, input().split()))
p = []
for i in range(M):
    tmp = list(map(int, input().split()))
    tmp.append(i)
    p.append(tmp)
p.sort()
ans = []
count = 1
for i in range(M):
    if p[i - 1][0] != p[i][0]:
        count = 1
    elif i != 0:
        count += 1
    id = str(p[i][0]).zfill(6) + str(count).zfill(6)
    ans.append((p[i][2], id))
ans.sort()
for i in ans:
    print((i[1]))

-array = [] +p = [] +for i in range(M): +    tmp = list(map(int, input().split())) +    tmp.append(i) +    p.append(tmp) +p.sort() -for i in range(M): -    array.append(list(map(int, input().split())) + [i]) -array.sort() -    id_left = str(array[i][0]) -    while len(id_left) < 6: -        id_left = "0" + id_left -    id_right = str(count) -    while len(id_right) < 6: -        id_right = "0" + id_right -    id = id_left + id_right -    ans.append([array[i][2], id]) -    if i == M - 1: -        break -    if array[i][0] != array[i + 1][0]: +    if p[i - 1][0] != p[i][0]: -    else: +    elif i != 0: +    id = str(p[i][0]).zfill(6) + str(count).zfill(6) +    ans.append((p[i][2], id))