from operator import attrgetter





class City:

    def __init__(self, p, y):

        self.p = p

        self.y = y



    def set_num(self, n):

        p = str(self.p)

        _p = list(p)

        l_p = len(_p)

        if l_p < 6:

            num = 6 - l_p

            for i in range(num):

                p = "0" + p



        n = str(n)

        _n = list(n)

        l_n = len(_n)

        if l_n < 6:

            num = 6 - l_n

            for i in range(num):

                n = "0" + n

        self.n = p+n





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

cities = []

for _ in range(M):

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

    cities.append(City(p, y))



pref_map = {}

for city in cities:

    if city.p in pref_map:

        pref_map[city.p].append(city)

    else:

        pref_map[city.p] = [city]



for v in list(pref_map.values()):

    _cities = sorted(v, key=attrgetter("y"))

    cnt = 1

    for _city in _cities:

        _city.set_num(cnt)

        cnt += 1



for city in cities:

    print((city.n))

from operator import attrgetter





class City:

    def __init__(self, p, y):

        self.p = p

        self.y = y



    def set_num(self, n):

        self.n = '{0:06d}'.format(self.p) + '{0:06d}'.format(n)





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

cities = []

for _ in range(M):

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

    cities.append(City(p, y))



pref_map = {}

for city in cities:

    if city.p in pref_map:

        pref_map[city.p].append(city)

    else:

        pref_map[city.p] = [city]



for v in list(pref_map.values()):

    _cities = sorted(v, key=attrgetter("y"))

    cnt = 1

    for _city in _cities:

        _city.set_num(cnt)

        cnt += 1



for city in cities:

    print((city.n))

from operator import attrgetter


class City:
    def __init__(self, p, y):
        self.p = p
        self.y = y

    def set_num(self, n):
        p = str(self.p)
        _p = list(p)
        l_p = len(_p)
        if l_p < 6:
            num = 6 - l_p
            for i in range(num):
                p = "0" + p
        n = str(n)
        _n = list(n)
        l_n = len(_n)
        if l_n < 6:
            num = 6 - l_n
            for i in range(num):
                n = "0" + n
        self.n = p + n


N, M = list(map(int, input().split()))
cities = []
for _ in range(M):
    p, y = list(map(int, input().split()))
    cities.append(City(p, y))
pref_map = {}
for city in cities:
    if city.p in pref_map:
        pref_map[city.p].append(city)
    else:
        pref_map[city.p] = [city]
for v in list(pref_map.values()):
    _cities = sorted(v, key=attrgetter("y"))
    cnt = 1
    for _city in _cities:
        _city.set_num(cnt)
        cnt += 1
for city in cities:
    print((city.n))

from operator import attrgetter


class City:
    def __init__(self, p, y):
        self.p = p
        self.y = y

    def set_num(self, n):
        self.n = "{0:06d}".format(self.p) + "{0:06d}".format(n)


N, M = list(map(int, input().split()))
cities = []
for _ in range(M):
    p, y = list(map(int, input().split()))
    cities.append(City(p, y))
pref_map = {}
for city in cities:
    if city.p in pref_map:
        pref_map[city.p].append(city)
    else:
        pref_map[city.p] = [city]
for v in list(pref_map.values()):
    _cities = sorted(v, key=attrgetter("y"))
    cnt = 1
    for _city in _cities:
        _city.set_num(cnt)
        cnt += 1
for city in cities:
    print((city.n))

-        p = str(self.p) -        _p = list(p) -        l_p = len(_p) -        if l_p < 6: -            num = 6 - l_p -            for i in range(num): -                p = "0" + p -        n = str(n) -        _n = list(n) -        l_n = len(_n) -        if l_n < 6: -            num = 6 - l_n -            for i in range(num): -                n = "0" + n -        self.n = p + n +        self.n = "{0:06d}".format(self.p) + "{0:06d}".format(n)