from collections import Counter



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

records = [tuple(map(int, input().split(' '))) for _ in range(M)]

s_records = sorted(records)



counter = Counter()

d = {}



for p, y in s_records:

    counter[p] += 1

    d[(p, y)] = '{:06}{:06}'.format(p, counter[p])



for p, y in records:

    print((d[(p, y)]))

import bisect

from collections import defaultdict



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

cities = []

years = defaultdict(list)

for _ in range(M):

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

    cities.append((p, y))

    years[p].append(y)



for p in list(years.keys()):

    years[p].sort()



for p, y in cities:

    print(('{:06}{:06}'.format(p, bisect.bisect_right(years[p], y))))

from collections import Counter

N, M = list(map(int, input().split(" ")))
records = [tuple(map(int, input().split(" "))) for _ in range(M)]
s_records = sorted(records)
counter = Counter()
d = {}
for p, y in s_records:
    counter[p] += 1
    d[(p, y)] = "{:06}{:06}".format(p, counter[p])
for p, y in records:
    print((d[(p, y)]))

import bisect
from collections import defaultdict

N, M = list(map(int, input().split(" ")))
cities = []
years = defaultdict(list)
for _ in range(M):
    p, y = list(map(int, input().split(" ")))
    cities.append((p, y))
    years[p].append(y)
for p in list(years.keys()):
    years[p].sort()
for p, y in cities:
    print(("{:06}{:06}".format(p, bisect.bisect_right(years[p], y))))

-from collections import Counter +import bisect +from collections import defaultdict -records = [tuple(map(int, input().split(" "))) for _ in range(M)] -s_records = sorted(records) -counter = Counter() -d = {} -for p, y in s_records: -    counter[p] += 1 -    d[(p, y)] = "{:06}{:06}".format(p, counter[p]) -for p, y in records: -    print((d[(p, y)])) +cities = [] +years = defaultdict(list) +for _ in range(M): +    p, y = list(map(int, input().split(" "))) +    cities.append((p, y)) +    years[p].append(y) +for p in list(years.keys()): +    years[p].sort() +for p, y in cities: +    print(("{:06}{:06}".format(p, bisect.bisect_right(years[p], y))))