n, m =list(map(int, input().split()))

py_array = [[int(x) for x in input().split()]+[y] for x, y in enumerate(list(range(m)), 0)]

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



base = 1

base2 = 0

res_array = []

for i, j, k in py_array:

    if base == i:

        base2 += 1

    else:

        base = i

        base2 = 1

    res_array.append([str(base).zfill(6), str(base2).zfill(6), k])



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



for i, j, k in res_array:

    print((i+j))
n, m = list(map(int, input().split()))

py_array = [[int(x) for x in input().split()] for y in range(m)]

py_dict = {x: y for x, y in enumerate(py_array, 1)}

py = sorted(list(py_dict.items()), key=lambda x: x[1][1])

ans = {}

now = min([x[0] for x in py_array])

index = 0

index_array = {x: 0 for x in [x[0] for x in py_array]}

for key, value in py:

    index_array[value[0]] += 1

    index = index_array[value[0]]

    ken = str(value[0])

    si = str(index)

    ans[key] = ken.zfill(6) + si.zfill(6)

    now = value[0]

for key, value in list(ans.items()):

    print(value)

n, m = list(map(int, input().split()))
py_array = [
    [int(x) for x in input().split()] + [y] for x, y in enumerate(list(range(m)), 0)
]
py_array = sorted(py_array, key=lambda x: (x[0], x[1]))
base = 1
base2 = 0
res_array = []
for i, j, k in py_array:
    if base == i:
        base2 += 1
    else:
        base = i
        base2 = 1
    res_array.append([str(base).zfill(6), str(base2).zfill(6), k])
res_array = sorted(res_array, key=lambda x: x[2])
for i, j, k in res_array:
    print((i + j))

n, m = list(map(int, input().split()))
py_array = [[int(x) for x in input().split()] for y in range(m)]
py_dict = {x: y for x, y in enumerate(py_array, 1)}
py = sorted(list(py_dict.items()), key=lambda x: x[1][1])
ans = {}
now = min([x[0] for x in py_array])
index = 0
index_array = {x: 0 for x in [x[0] for x in py_array]}
for key, value in py:
    index_array[value[0]] += 1
    index = index_array[value[0]]
    ken = str(value[0])
    si = str(index)
    ans[key] = ken.zfill(6) + si.zfill(6)
    now = value[0]
for key, value in list(ans.items()):
    print(value)

-py_array = [ -    [int(x) for x in input().split()] + [y] for x, y in enumerate(list(range(m)), 0) -] -py_array = sorted(py_array, key=lambda x: (x[0], x[1])) -base = 1 -base2 = 0 -res_array = [] -for i, j, k in py_array: -    if base == i: -        base2 += 1 -    else: -        base = i -        base2 = 1 -    res_array.append([str(base).zfill(6), str(base2).zfill(6), k]) -res_array = sorted(res_array, key=lambda x: x[2]) -for i, j, k in res_array: -    print((i + j)) +py_array = [[int(x) for x in input().split()] for y in range(m)] +py_dict = {x: y for x, y in enumerate(py_array, 1)} +py = sorted(list(py_dict.items()), key=lambda x: x[1][1]) +ans = {} +now = min([x[0] for x in py_array]) +index = 0 +index_array = {x: 0 for x in [x[0] for x in py_array]} +for key, value in py: +    index_array[value[0]] += 1 +    index = index_array[value[0]] +    ken = str(value[0]) +    si = str(index) +    ans[key] = ken.zfill(6) + si.zfill(6) +    now = value[0] +for key, value in list(ans.items()): +    print(value)