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



lst = []

for i in range(M):

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

    a += [i] #i: 市の番号

    lst += [a]

#print (lst)

lst.sort()

#print (lst)



ken = -1

x = 0

ans = []

for j in range(M):

    if ken != lst[j][0]: #1つ前と市の名前が違う

        x = 1 #

        ken = lst[j][0]

#        P = '{:0>6}'.format(ken)

        #print ('A')

    else: #1つ前と市の名前が同じ

        x += 1

        #print ('B')

#    X = '{:0>6}'.format(x)

    ans += [[lst[j][2], ken, x]]



ans.sort()

#print (ans)

for k in range(M):

    P = '{:0>6}'.format(ans[k][1])

    X = '{:0>6}'.format(ans[k][2])

    print((P+X))
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 = '')

N, M = list(map(int, input().split()))
lst = []
for i in range(M):
    a = list(map(int, input().split()))
    a += [i]  # i: 市の番号
    lst += [a]
# print (lst)
lst.sort()
# print (lst)
ken = -1
x = 0
ans = []
for j in range(M):
    if ken != lst[j][0]:  # 1つ前と市の名前が違う
        x = 1  #
        ken = lst[j][0]
    #        P = '{:0>6}'.format(ken)
    # print ('A')
    else:  # 1つ前と市の名前が同じ
        x += 1
        # print ('B')
    #    X = '{:0>6}'.format(x)
    ans += [[lst[j][2], ken, x]]
ans.sort()
# print (ans)
for k in range(M):
    P = "{:0>6}".format(ans[k][1])
    X = "{:0>6}".format(ans[k][2])
    print((P + X))

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="")

-N, M = list(map(int, input().split())) -lst = [] -for i in range(M): -    a = list(map(int, input().split())) -    a += [i]  # i: 市の番号 -    lst += [a] -# print (lst) -lst.sort() -# print (lst) -ken = -1 -x = 0 -ans = [] -for j in range(M): -    if ken != lst[j][0]:  # 1つ前と市の名前が違う -        x = 1  # -        ken = lst[j][0] -    #        P = '{:0>6}'.format(ken) -    # print ('A') -    else:  # 1つ前と市の名前が同じ +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]) -        # print ('B') -    #    X = '{:0>6}'.format(x) -    ans += [[lst[j][2], ken, x]] -ans.sort() -# print (ans) -for k in range(M): -    P = "{:0>6}".format(ans[k][1]) -    X = "{:0>6}".format(ans[k][2]) -    print((P + X)) +    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="")