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

a = [[] for _ in range(N + 1)]



for i in range(M):

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

    a[p].append((y, i))



ans = [None for _ in range(M)]

for p in range(1, N + 1):

    for e, (y, i) in enumerate(sorted(a[p], key=lambda x: x[0]), 1):

        ans[i] = str(p).zfill(6) + str(e).zfill(6)



for i in range(M):

    print((ans[i]))

from collections import defaultdict

from operator import itemgetter



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



d = defaultdict(list)

for query_idx in range(m):

    pref_idx, year = map(int, input().split())

    d[pref_idx].append((year, query_idx))



ans = [None] * m

for pref_idx in d.keys():

    d[pref_idx].sort(key=itemgetter(0))

    # 県別誕生年昇順ソート

    for city_idx, (year, query_idx) in enumerate(d[pref_idx], 1):

        ans[query_idx] = '{:0>6}{:0>6}'.format(pref_idx, city_idx)

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

N, M = list(map(int, input().split()))
a = [[] for _ in range(N + 1)]
for i in range(M):
    p, y = list(map(int, input().split()))
    a[p].append((y, i))
ans = [None for _ in range(M)]
for p in range(1, N + 1):
    for e, (y, i) in enumerate(sorted(a[p], key=lambda x: x[0]), 1):
        ans[i] = str(p).zfill(6) + str(e).zfill(6)
for i in range(M):
    print((ans[i]))

from collections import defaultdict
from operator import itemgetter

n, m = map(int, input().split())
d = defaultdict(list)
for query_idx in range(m):
    pref_idx, year = map(int, input().split())
    d[pref_idx].append((year, query_idx))
ans = [None] * m
for pref_idx in d.keys():
    d[pref_idx].sort(key=itemgetter(0))
    # 県別誕生年昇順ソート
    for city_idx, (year, query_idx) in enumerate(d[pref_idx], 1):
        ans[query_idx] = "{:0>6}{:0>6}".format(pref_idx, city_idx)
print(*ans, sep="\n")

-N, M = list(map(int, input().split())) -a = [[] for _ in range(N + 1)] -for i in range(M): -    p, y = list(map(int, input().split())) -    a[p].append((y, i)) -ans = [None for _ in range(M)] -for p in range(1, N + 1): -    for e, (y, i) in enumerate(sorted(a[p], key=lambda x: x[0]), 1): -        ans[i] = str(p).zfill(6) + str(e).zfill(6) -for i in range(M): -    print((ans[i])) +from collections import defaultdict +from operator import itemgetter + +n, m = map(int, input().split()) +d = defaultdict(list) +for query_idx in range(m): +    pref_idx, year = map(int, input().split()) +    d[pref_idx].append((year, query_idx)) +ans = [None] * m +for pref_idx in d.keys(): +    d[pref_idx].sort(key=itemgetter(0)) +    # 県別誕生年昇順ソート +    for city_idx, (year, query_idx) in enumerate(d[pref_idx], 1): +        ans[query_idx] = "{:0>6}{:0>6}".format(pref_idx, city_idx) +print(*ans, sep="\n")