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

L=[]

for i in range(m):

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

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

L.sort(key=lambda L:(L[0],L[1]))

L[0][1]=1

for i in range(1,m):

    if L[i][0]!=L[i-1][0]:

        L[i][1]=1

    else:

        L[i][1]=L[i-1][1]+1

L.sort(key=lambda L:L[2])

for i in range(m):

    print(('{h1:0=6}{h2:0=6}'.format(h1=L[i][0],h2=L[i][1])))   



from collections import defaultdict

from bisect import bisect_left



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

years = defaultdict(list)

sorted_years = defaultdict(list)

PY = []

for i in range(m):

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

    years[prefecture].append(year)

    PY.append((prefecture, year))



for prefecture, year_list in list(years.items()):

    temp = year_list

    temp.sort()

    sorted_years[prefecture] = temp



for pair in PY:

    p, y = pair

    years[p]

    num = 1 + bisect_left(sorted_years[p], y)

    print((str(p).zfill(6) + str(num).zfill(6)))

n, m = list(map(int, input().split()))
L = []
for i in range(m):
    p, y = list(map(int, input().split()))
    L.append([p, y, i])
L.sort(key=lambda L: (L[0], L[1]))
L[0][1] = 1
for i in range(1, m):
    if L[i][0] != L[i - 1][0]:
        L[i][1] = 1
    else:
        L[i][1] = L[i - 1][1] + 1
L.sort(key=lambda L: L[2])
for i in range(m):
    print(("{h1:0=6}{h2:0=6}".format(h1=L[i][0], h2=L[i][1])))

from collections import defaultdict
from bisect import bisect_left

n, m = list(map(int, input().split()))
years = defaultdict(list)
sorted_years = defaultdict(list)
PY = []
for i in range(m):
    prefecture, year = list(map(int, input().split()))
    years[prefecture].append(year)
    PY.append((prefecture, year))
for prefecture, year_list in list(years.items()):
    temp = year_list
    temp.sort()
    sorted_years[prefecture] = temp
for pair in PY:
    p, y = pair
    years[p]
    num = 1 + bisect_left(sorted_years[p], y)
    print((str(p).zfill(6) + str(num).zfill(6)))

+from collections import defaultdict +from bisect import bisect_left + -L = [] +years = defaultdict(list) +sorted_years = defaultdict(list) +PY = [] -    p, y = list(map(int, input().split())) -    L.append([p, y, i]) -L.sort(key=lambda L: (L[0], L[1])) -L[0][1] = 1 -for i in range(1, m): -    if L[i][0] != L[i - 1][0]: -        L[i][1] = 1 -    else: -        L[i][1] = L[i - 1][1] + 1 -L.sort(key=lambda L: L[2]) -for i in range(m): -    print(("{h1:0=6}{h2:0=6}".format(h1=L[i][0], h2=L[i][1]))) +    prefecture, year = list(map(int, input().split())) +    years[prefecture].append(year) +    PY.append((prefecture, year)) +for prefecture, year_list in list(years.items()): +    temp = year_list +    temp.sort() +    sorted_years[prefecture] = temp +for pair in PY: +    p, y = pair +    years[p] +    num = 1 + bisect_left(sorted_years[p], y) +    print((str(p).zfill(6) + str(num).zfill(6)))