import sys

fin = sys.stdin.readline

from collections import defaultdict





N, M = [int(elem) for elem in fin().split()]

pref_years = [[int(elem) for elem in fin().split()] for _ in range(M)]

formatter = lambda x: "{:06}".format(x)



# sort by year in ascending order

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

number_cities_per_city = defaultdict(int)

identity_numbers = {}

for pref, year in sorted_pref_years:

    number_cities_per_city[pref] += 1

    identity_numbers[year] = formatter(pref) \

                           + formatter(number_cities_per_city[pref])



for _, year in pref_years:

    print(identity_numbers[year])

import sys

fin = sys.stdin.readline

from collections import defaultdict





N, M = [int(elem) for elem in fin().split()]

cities = [[int(elem) for elem in fin().split()] for _ in range(M)]

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



num_cities_in_pref = defaultdict(int)

years_to_identification = dict()

for pref, year in sorted_cities:

    num_cities_in_pref[pref] += 1

    years_to_identification[year] = "{:06}{:06}".format(pref, num_cities_in_pref[pref])



for _, year in cities:

    print((years_to_identification[year]))

import sys

fin = sys.stdin.readline
from collections import defaultdict

N, M = [int(elem) for elem in fin().split()]
pref_years = [[int(elem) for elem in fin().split()] for _ in range(M)]
formatter = lambda x: "{:06}".format(x)
# sort by year in ascending order
sorted_pref_years = sorted(pref_years, key=lambda x: x[1])
number_cities_per_city = defaultdict(int)
identity_numbers = {}
for pref, year in sorted_pref_years:
    number_cities_per_city[pref] += 1
    identity_numbers[year] = formatter(pref) + formatter(number_cities_per_city[pref])
for _, year in pref_years:
    print(identity_numbers[year])

import sys

fin = sys.stdin.readline
from collections import defaultdict

N, M = [int(elem) for elem in fin().split()]
cities = [[int(elem) for elem in fin().split()] for _ in range(M)]
sorted_cities = sorted(cities, key=lambda x: x[1])
num_cities_in_pref = defaultdict(int)
years_to_identification = dict()
for pref, year in sorted_cities:
    num_cities_in_pref[pref] += 1
    years_to_identification[year] = "{:06}{:06}".format(pref, num_cities_in_pref[pref])
for _, year in cities:
    print((years_to_identification[year]))

-pref_years = [[int(elem) for elem in fin().split()] for _ in range(M)] -formatter = lambda x: "{:06}".format(x) -# sort by year in ascending order -sorted_pref_years = sorted(pref_years, key=lambda x: x[1]) -number_cities_per_city = defaultdict(int) -identity_numbers = {} -for pref, year in sorted_pref_years: -    number_cities_per_city[pref] += 1 -    identity_numbers[year] = formatter(pref) + formatter(number_cities_per_city[pref]) -for _, year in pref_years: -    print(identity_numbers[year]) +cities = [[int(elem) for elem in fin().split()] for _ in range(M)] +sorted_cities = sorted(cities, key=lambda x: x[1]) +num_cities_in_pref = defaultdict(int) +years_to_identification = dict() +for pref, year in sorted_cities: +    num_cities_in_pref[pref] += 1 +    years_to_identification[year] = "{:06}{:06}".format(pref, num_cities_in_pref[pref]) +for _, year in cities: +    print((years_to_identification[year]))