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



cities = [[] for _ in range(N)]



for i in range(M) :

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

    cities[p - 1].append((i, y))



id = [0] * M



for p, city in enumerate(cities) :

    city.sort(key = lambda A : A[1])

    for index, (i, year) in enumerate(city) :

        id[i] = '{pre:06}{i:06}'.format(pre = p + 1, i = index + 1)



for i in range(M) :

    print((id[i]))
from collections import defaultdict



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



A = defaultdict(list)

for i in range(M):

    P, Y = map(int, input().split())

    A[P].append((Y, i))



ans = [''] * M

for p, grp in A.items():

    for j, (_, i) in enumerate(sorted(grp), start=1):

        ans[i] = '%06d%06d' % (p, j)

print(*ans, sep='\n')



N, M = list(map(int, input().split()))
cities = [[] for _ in range(N)]
for i in range(M):
    p, y = list(map(int, input().split()))
    cities[p - 1].append((i, y))
id = [0] * M
for p, city in enumerate(cities):
    city.sort(key=lambda A: A[1])
    for index, (i, year) in enumerate(city):
        id[i] = "{pre:06}{i:06}".format(pre=p + 1, i=index + 1)
for i in range(M):
    print((id[i]))

from collections import defaultdict

N, M = map(int, input().split())
A = defaultdict(list)
for i in range(M):
    P, Y = map(int, input().split())
    A[P].append((Y, i))
ans = [""] * M
for p, grp in A.items():
    for j, (_, i) in enumerate(sorted(grp), start=1):
        ans[i] = "%06d%06d" % (p, j)
print(*ans, sep="\n")

-N, M = list(map(int, input().split())) -cities = [[] for _ in range(N)] +from collections import defaultdict + +N, M = map(int, input().split()) +A = defaultdict(list) -    p, y = list(map(int, input().split())) -    cities[p - 1].append((i, y)) -id = [0] * M -for p, city in enumerate(cities): -    city.sort(key=lambda A: A[1]) -    for index, (i, year) in enumerate(city): -        id[i] = "{pre:06}{i:06}".format(pre=p + 1, i=index + 1) -for i in range(M): -    print((id[i])) +    P, Y = map(int, input().split()) +    A[P].append((Y, i)) +ans = [""] * M +for p, grp in A.items(): +    for j, (_, i) in enumerate(sorted(grp), start=1): +        ans[i] = "%06d%06d" % (p, j) +print(*ans, sep="\n")