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

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

PY.sort(key = lambda x: x[1])

PY.sort(key = lambda x: x[0])



ans_lst = []

x = 1

tmp_p = None

for p, y, i in PY:

    if p == tmp_p: #属している県が同じ時

        ans_lst.append([p, x, i])

        x += 1

    else:

        ans_lst.append([p, 1, i])

        tmp_p = p

        x = 2



ans_lst.sort(key = lambda x: x[2])





#output

for p, x, i in ans_lst:

    ans_p = str('000000') + str(p)

    ans_x = str('000000') + str(x)

    # print (ans_p, ans_x)

    # print (ans_p[-6:])

    print (ans_p[-6:], ans_x[-6:], sep = '')

import sys

input = sys.stdin.readline



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



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

# print (lst)



lst.sort(key = lambda x: x[1]) #x番目が小さい順に並べる

lst.sort(key = lambda x: x[0])





ans = [0] * M



count = 0

tmp = 0 #１つ前の県の番号

for p, y, i in lst:

    if tmp == p:

        count += 1

    else:

        count = 1

        tmp = p

    tmp_ans = str(p).zfill(6) + str(count).zfill(6)

    ans[i] = tmp_ans



print (*ans, sep = '\n')







N, M = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]
PY.sort(key=lambda x: x[1])
PY.sort(key=lambda x: x[0])
ans_lst = []
x = 1
tmp_p = None
for p, y, i in PY:
    if p == tmp_p:  # 属している県が同じ時
        ans_lst.append([p, x, i])
        x += 1
    else:
        ans_lst.append([p, 1, i])
        tmp_p = p
        x = 2
ans_lst.sort(key=lambda x: x[2])
# output
for p, x, i in ans_lst:
    ans_p = str("000000") + str(p)
    ans_x = str("000000") + str(x)
    # print (ans_p, ans_x)
    # print (ans_p[-6:])
    print(ans_p[-6:], ans_x[-6:], sep="")

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
lst = [list(map(int, input().split())) + [i] for i in range(M)]
# print (lst)
lst.sort(key=lambda x: x[1])  # x番目が小さい順に並べる
lst.sort(key=lambda x: x[0])
ans = [0] * M
count = 0
tmp = 0  # １つ前の県の番号
for p, y, i in lst:
    if tmp == p:
        count += 1
    else:
        count = 1
        tmp = p
    tmp_ans = str(p).zfill(6) + str(count).zfill(6)
    ans[i] = tmp_ans
print(*ans, sep="\n")

+import sys + +input = sys.stdin.readline -PY = [list(map(int, input().split())) + [i] for i in range(M)] -PY.sort(key=lambda x: x[1]) -PY.sort(key=lambda x: x[0]) -ans_lst = [] -x = 1 -tmp_p = None -for p, y, i in PY: -    if p == tmp_p:  # 属している県が同じ時 -        ans_lst.append([p, x, i]) -        x += 1 +lst = [list(map(int, input().split())) + [i] for i in range(M)] +# print (lst) +lst.sort(key=lambda x: x[1])  # x番目が小さい順に並べる +lst.sort(key=lambda x: x[0]) +ans = [0] * M +count = 0 +tmp = 0  # １つ前の県の番号 +for p, y, i in lst: +    if tmp == p: +        count += 1 -        ans_lst.append([p, 1, i]) -        tmp_p = p -        x = 2 -ans_lst.sort(key=lambda x: x[2]) -# output -for p, x, i in ans_lst: -    ans_p = str("000000") + str(p) -    ans_x = str("000000") + str(x) -    # print (ans_p, ans_x) -    # print (ans_p[-6:]) -    print(ans_p[-6:], ans_x[-6:], sep="") +        count = 1 +        tmp = p +    tmp_ans = str(p).zfill(6) + str(count).zfill(6) +    ans[i] = tmp_ans +print(*ans, sep="\n")