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

cities = []

for _ in range(m):

    cities.append(list(map(int, input().split())))



city_dict = {}

for i, city in enumerate(cities):

    if not city[0] in city_dict:

        city_dict[city[0]] = []

    city_dict[city[0]].append([i, city[1], ""])



ans = []

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

    value.sort(key=lambda x: x[1])

    for i, v in enumerate(value):

        v[2] = "{}{}".format(str(key).zfill(6), str(i+1).zfill(6))

    ans.extend(value)

ans.sort(key=lambda x:x[0])

for a in ans:

    print((a[2]))
(n, m) = list(map(int, input().split()))

cities = {}

for i in range(m):

    (pref, year) = list(map(int, input().split()))

    if not pref in list(cities.keys()):

        cities[pref] = []

    cities[pref].append((i, year))





def get_id(pref, index):

    return "{}{}".format(str(pref).zfill(6), str(index).zfill(6))





ids = []

for key, values in list(cities.items()):

    values.sort(key=lambda x: x[1])

    for i, value in enumerate(values):

        ids.append((value[0], get_id(key, i + 1)))

ids.sort(key=lambda x: x[0])

for id in ids:

    print((id[1]))

(n, m) = list(map(int, input().split()))
cities = []
for _ in range(m):
    cities.append(list(map(int, input().split())))
city_dict = {}
for i, city in enumerate(cities):
    if not city[0] in city_dict:
        city_dict[city[0]] = []
    city_dict[city[0]].append([i, city[1], ""])
ans = []
for key, value in list(city_dict.items()):
    value.sort(key=lambda x: x[1])
    for i, v in enumerate(value):
        v[2] = "{}{}".format(str(key).zfill(6), str(i + 1).zfill(6))
    ans.extend(value)
ans.sort(key=lambda x: x[0])
for a in ans:
    print((a[2]))

(n, m) = list(map(int, input().split()))
cities = {}
for i in range(m):
    (pref, year) = list(map(int, input().split()))
    if not pref in list(cities.keys()):
        cities[pref] = []
    cities[pref].append((i, year))


def get_id(pref, index):
    return "{}{}".format(str(pref).zfill(6), str(index).zfill(6))


ids = []
for key, values in list(cities.items()):
    values.sort(key=lambda x: x[1])
    for i, value in enumerate(values):
        ids.append((value[0], get_id(key, i + 1)))
ids.sort(key=lambda x: x[0])
for id in ids:
    print((id[1]))

-cities = [] -for _ in range(m): -    cities.append(list(map(int, input().split()))) -city_dict = {} -for i, city in enumerate(cities): -    if not city[0] in city_dict: -        city_dict[city[0]] = [] -    city_dict[city[0]].append([i, city[1], ""]) -ans = [] -for key, value in list(city_dict.items()): -    value.sort(key=lambda x: x[1]) -    for i, v in enumerate(value): -        v[2] = "{}{}".format(str(key).zfill(6), str(i + 1).zfill(6)) -    ans.extend(value) -ans.sort(key=lambda x: x[0]) -for a in ans: -    print((a[2])) +cities = {} +for i in range(m): +    (pref, year) = list(map(int, input().split())) +    if not pref in list(cities.keys()): +        cities[pref] = [] +    cities[pref].append((i, year)) + + +def get_id(pref, index): +    return "{}{}".format(str(pref).zfill(6), str(index).zfill(6)) + + +ids = [] +for key, values in list(cities.items()): +    values.sort(key=lambda x: x[1]) +    for i, value in enumerate(values): +        ids.append((value[0], get_id(key, i + 1))) +ids.sort(key=lambda x: x[0]) +for id in ids: +    print((id[1]))