# -*- coding: utf-8 -*-



# from time import time

# 

# start = time()





def six(n):

    n_str = str(n)

    while len(n_str) < 6:

        n_str = "0" + n_str



    return n_str





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



id_list = [None] * M

dic_P = {}

info = []

info_idx = 0



for i in range(M):

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

    id_list[i] = [P, Y, ""]

    if P in list(dic_P.keys()):

        info[dic_P[P]].append([i, P, Y])

    else:

        dic_P[P] = info_idx

        info_idx += 1

        info.append([[i, P, Y]])



for group in info:

    group.sort(key=lambda a_i: a_i[2], reverse=False)

    for i, pair in enumerate(group):

        id = six(pair[1]) + six(i+1)

        id_list[pair[0]] = id



for id in id_list:

    print(id)



# print(time() - start)

# -*- coding: utf-8 -*-



# from time import time

# 

# start = time()





def six(n):

    n_str = str(n)

    while len(n_str) < 6:

        n_str = "0" + n_str



    return n_str





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



id_list = [None] * M

dic_P = {}

info = []

info_idx = 0



for i in range(M):

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

    if P in list(dic_P.keys()):

        info[dic_P[P]].append([i, P, Y])

    else:

        dic_P[P] = info_idx

        info_idx += 1

        info.append([[i, P, Y]])



for group in info:

    group.sort(key=lambda a_i: a_i[2], reverse=False)

    for i, pair in enumerate(group):

        id = six(pair[1]) + six(i+1)

        id_list[pair[0]] = id



for id in id_list:

    print(id)



# print(time() - start)

# -*- coding: utf-8 -*-
# from time import time
#
# start = time()
def six(n):
    n_str = str(n)
    while len(n_str) < 6:
        n_str = "0" + n_str
    return n_str


N, M = list(map(int, input().split()))
id_list = [None] * M
dic_P = {}
info = []
info_idx = 0
for i in range(M):
    P, Y = list(map(int, input().split()))
    id_list[i] = [P, Y, ""]
    if P in list(dic_P.keys()):
        info[dic_P[P]].append([i, P, Y])
    else:
        dic_P[P] = info_idx
        info_idx += 1
        info.append([[i, P, Y]])
for group in info:
    group.sort(key=lambda a_i: a_i[2], reverse=False)
    for i, pair in enumerate(group):
        id = six(pair[1]) + six(i + 1)
        id_list[pair[0]] = id
for id in id_list:
    print(id)
# print(time() - start)

# -*- coding: utf-8 -*-
# from time import time
#
# start = time()
def six(n):
    n_str = str(n)
    while len(n_str) < 6:
        n_str = "0" + n_str
    return n_str


N, M = list(map(int, input().split()))
id_list = [None] * M
dic_P = {}
info = []
info_idx = 0
for i in range(M):
    P, Y = list(map(int, input().split()))
    if P in list(dic_P.keys()):
        info[dic_P[P]].append([i, P, Y])
    else:
        dic_P[P] = info_idx
        info_idx += 1
        info.append([[i, P, Y]])
for group in info:
    group.sort(key=lambda a_i: a_i[2], reverse=False)
    for i, pair in enumerate(group):
        id = six(pair[1]) + six(i + 1)
        id_list[pair[0]] = id
for id in id_list:
    print(id)
# print(time() - start)

-    id_list[i] = [P, Y, ""]