import bisect



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

years = [[]for i in range(n)]

yearss = []



for i in range(m):

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

  years[p-1].append(y)

  yearss.append([p,y])





for i in range(n):

  years[i].sort()



for i in range(m):

  print("{0:06d}".format(yearss[i][0]),"{0:06d}".format(bisect.bisect_right(years[yearss[i][0]-1],yearss[i][1])),sep="")

from bisect import bisect_left

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

ls=[[] for i in range(n)]

py=[]

for i in range(m):

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

  ls[p-1].append(y)

  py.append([p,y])

ls=list([sorted(x) for x in ls])

for i in range(m):

  p,y=py[i]

  index= bisect_left(ls[p-1],y)

  print((str(p).zfill(6)+str(index+1).zfill(6)))

import bisect

n, m = map(int, input().split())
years = [[] for i in range(n)]
yearss = []
for i in range(m):
    p, y = map(int, input().split())
    years[p - 1].append(y)
    yearss.append([p, y])
for i in range(n):
    years[i].sort()
for i in range(m):
    print(
        "{0:06d}".format(yearss[i][0]),
        "{0:06d}".format(bisect.bisect_right(years[yearss[i][0] - 1], yearss[i][1])),
        sep="",
    )

from bisect import bisect_left

n, m = list(map(int, input().split()))
ls = [[] for i in range(n)]
py = []
for i in range(m):
    p, y = list(map(int, input().split()))
    ls[p - 1].append(y)
    py.append([p, y])
ls = list([sorted(x) for x in ls])
for i in range(m):
    p, y = py[i]
    index = bisect_left(ls[p - 1], y)
    print((str(p).zfill(6) + str(index + 1).zfill(6)))

-import bisect +from bisect import bisect_left -n, m = map(int, input().split()) -years = [[] for i in range(n)] -yearss = [] +n, m = list(map(int, input().split())) +ls = [[] for i in range(n)] +py = [] -    p, y = map(int, input().split()) -    years[p - 1].append(y) -    yearss.append([p, y]) -for i in range(n): -    years[i].sort() +    p, y = list(map(int, input().split())) +    ls[p - 1].append(y) +    py.append([p, y]) +ls = list([sorted(x) for x in ls]) -    print( -        "{0:06d}".format(yearss[i][0]), -        "{0:06d}".format(bisect.bisect_right(years[yearss[i][0] - 1], yearss[i][1])), -        sep="", -    ) +    p, y = py[i] +    index = bisect_left(ls[p - 1], y) +    print((str(p).zfill(6) + str(index + 1).zfill(6)))