debug = 0

"""

N: state num

M: city num

"""





if debug:

    N = 2

    m = 10

else:

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



if debug:

    p_y_list = [

        [1, 30]

        ,[1, 20]

        ,[1, 10]

        ,[1, 3]

        ,[2, 63]

        ,[2, 33]

        ,[2, 23]

        ,[3, 21]

        ,[3, 7]

    ]



city_id_list = []

for num, z in enumerate(range(M)):

# for num, (P, Y) in enumerate(p_y_list):

    

    if not debug:

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



    city_id_list.append([Y, P, num])

    

city_id_list = sorted( city_id_list, key= lambda x: x[0])



state_cnt = {}

tmp_list = []

for (Y, P, num) in city_id_list:

    

    if P not in list(state_cnt.keys()):

        state_cnt[P] = 1

    elif P in list(state_cnt.keys()):

        state_cnt[P] += 1

        

    tmp_id = str(P).zfill(6) + str(state_cnt[P]).zfill(6)

    

    tmp_list.append([num, tmp_id])

    

for cid in sorted(tmp_list, key=lambda x: x[0]):

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



cities = []

for i in range(M):

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

    cities.append([p, y, i])



cities = sorted(cities, key=lambda x: x[1])

cities = sorted(cities, key=lambda x: x[0])



p = cities[0][0]

cnt = 1

for i in range(M):



    if (cities[i][0] == p):

        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))

        cnt += 1

    else:

        p = cities[i][0]

        cnt = 1

        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))

        cnt += 1



cities = sorted(cities, key=lambda x: x[2])



for i in range(M):

    print((cities[i][3]))

debug = 0
"""
N: state num
M: city num
"""
if debug:
    N = 2
    m = 10
else:
    (N, M) = list(map(int, input().split()))
if debug:
    p_y_list = [
        [1, 30],
        [1, 20],
        [1, 10],
        [1, 3],
        [2, 63],
        [2, 33],
        [2, 23],
        [3, 21],
        [3, 7],
    ]
city_id_list = []
for num, z in enumerate(range(M)):
    # for num, (P, Y) in enumerate(p_y_list):
    if not debug:
        (P, Y) = list(map(int, input().split()))
    city_id_list.append([Y, P, num])
city_id_list = sorted(city_id_list, key=lambda x: x[0])
state_cnt = {}
tmp_list = []
for (Y, P, num) in city_id_list:
    if P not in list(state_cnt.keys()):
        state_cnt[P] = 1
    elif P in list(state_cnt.keys()):
        state_cnt[P] += 1
    tmp_id = str(P).zfill(6) + str(state_cnt[P]).zfill(6)
    tmp_list.append([num, tmp_id])
for cid in sorted(tmp_list, key=lambda x: x[0]):
    print((cid[1]))

N, M = list(map(int, input().split(" ")))
cities = []
for i in range(M):
    p, y = list(map(int, input().split(" ")))
    cities.append([p, y, i])
cities = sorted(cities, key=lambda x: x[1])
cities = sorted(cities, key=lambda x: x[0])
p = cities[0][0]
cnt = 1
for i in range(M):
    if cities[i][0] == p:
        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))
        cnt += 1
    else:
        p = cities[i][0]
        cnt = 1
        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))
        cnt += 1
cities = sorted(cities, key=lambda x: x[2])
for i in range(M):
    print((cities[i][3]))

-debug = 0 -""" -N: state num -M: city num -""" -if debug: -    N = 2 -    m = 10 -else: -    (N, M) = list(map(int, input().split())) -if debug: -    p_y_list = [ -        [1, 30], -        [1, 20], -        [1, 10], -        [1, 3], -        [2, 63], -        [2, 33], -        [2, 23], -        [3, 21], -        [3, 7], -    ] -city_id_list = [] -for num, z in enumerate(range(M)): -    # for num, (P, Y) in enumerate(p_y_list): -    if not debug: -        (P, Y) = list(map(int, input().split())) -    city_id_list.append([Y, P, num]) -city_id_list = sorted(city_id_list, key=lambda x: x[0]) -state_cnt = {} -tmp_list = [] -for (Y, P, num) in city_id_list: -    if P not in list(state_cnt.keys()): -        state_cnt[P] = 1 -    elif P in list(state_cnt.keys()): -        state_cnt[P] += 1 -    tmp_id = str(P).zfill(6) + str(state_cnt[P]).zfill(6) -    tmp_list.append([num, tmp_id]) -for cid in sorted(tmp_list, key=lambda x: x[0]): -    print((cid[1])) +N, M = list(map(int, input().split(" "))) +cities = [] +for i in range(M): +    p, y = list(map(int, input().split(" "))) +    cities.append([p, y, i]) +cities = sorted(cities, key=lambda x: x[1]) +cities = sorted(cities, key=lambda x: x[0]) +p = cities[0][0] +cnt = 1 +for i in range(M): +    if cities[i][0] == p: +        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6)) +        cnt += 1 +    else: +        p = cities[i][0] +        cnt = 1 +        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6)) +        cnt += 1 +cities = sorted(cities, key=lambda x: x[2]) +for i in range(M): +    print((cities[i][3]))