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



ans=[[] for i in range(m)]

p_list=[[] for i in range(n+1)]



for i in range(m):

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



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



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



for pp in p_list:

 pp=sorted(pp,key=lambda x:x[1])

 num=0

 for ppp in pp:

  num+=1

  ans[ppp[0]]+=str(num).zfill(6)

 num=0



for i in ans:

 print(i)
from sys import stdin

nii=lambda:list(map(int,stdin.readline().split()))

lnii=lambda:list(map(int,stdin.readline()).split())



n,m=nii()



list=[[] for i in range(n+1)]



for i in range(m):

  p,y=nii()

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



ans=[]

for i in range(1,n+1):

  tl=list[i]

  s_tl=sorted(tl,key=lambda x:x[0])

  for j in range(len(tl)):

    town=s_tl[j][1]

    s1=str(i).zfill(6)

    s2=str(j+1).zfill(6)

    s=s1+s2

    ans.append([town,s])



ans.sort(key=lambda x:x[0])

for i,j in ans:

  print(j)
n, m = list(map(int, input().split()))
ans = [[] for i in range(m)]
p_list = [[] for i in range(n + 1)]
for i in range(m):
    p, y = list(map(int, input().split()))
    ans[i] = str(p).zfill(6)
    p_list[p].append([i, y])
for pp in p_list:
    pp = sorted(pp, key=lambda x: x[1])
    num = 0
    for ppp in pp:
        num += 1
        ans[ppp[0]] += str(num).zfill(6)
    num = 0
for i in ans:
    print(i)

from sys import stdin

nii = lambda: list(map(int, stdin.readline().split()))
lnii = lambda: list(map(int, stdin.readline()).split())
n, m = nii()
list = [[] for i in range(n + 1)]
for i in range(m):
    p, y = nii()
    list[p].append([y, i])
ans = []
for i in range(1, n + 1):
    tl = list[i]
    s_tl = sorted(tl, key=lambda x: x[0])
    for j in range(len(tl)):
        town = s_tl[j][1]
        s1 = str(i).zfill(6)
        s2 = str(j + 1).zfill(6)
        s = s1 + s2
        ans.append([town, s])
ans.sort(key=lambda x: x[0])
for i, j in ans:
    print(j)

-n, m = list(map(int, input().split())) -ans = [[] for i in range(m)] -p_list = [[] for i in range(n + 1)] +from sys import stdin + +nii = lambda: list(map(int, stdin.readline().split())) +lnii = lambda: list(map(int, stdin.readline()).split()) +n, m = nii() +list = [[] for i in range(n + 1)] -    p, y = list(map(int, input().split())) -    ans[i] = str(p).zfill(6) -    p_list[p].append([i, y]) -for pp in p_list: -    pp = sorted(pp, key=lambda x: x[1]) -    num = 0 -    for ppp in pp: -        num += 1 -        ans[ppp[0]] += str(num).zfill(6) -    num = 0 -for i in ans: -    print(i) +    p, y = nii() +    list[p].append([y, i]) +ans = [] +for i in range(1, n + 1): +    tl = list[i] +    s_tl = sorted(tl, key=lambda x: x[0]) +    for j in range(len(tl)): +        town = s_tl[j][1] +        s1 = str(i).zfill(6) +        s2 = str(j + 1).zfill(6) +        s = s1 + s2 +        ans.append([town, s]) +ans.sort(key=lambda x: x[0]) +for i, j in ans: +    print(j)