I=lambda:list(map(int,input().split()))

n,m=I()

a=[[i]+I() for i in range(m)]

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

b=[]

j0=0

p=1

for i,j,k in a:

  if j!=j0:

    p=1

  else:

    p+=1

  b.append([i,j,p])

  j0=j

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

for i,j,k in b:

  print(("{:06d}{:06d}".format(j,k)))
I=lambda:list(map(int,input().split()))

n,m=I()

a=[[i]+I() for i in range(m)]

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

b=[]

j0=0

p=1

for i,j,k in a:

  p=1 if j!=j0 else p+1

  b.append([i,j,p])

  j0=j

  

for i,j,k in sorted(b):

  print(("{:06d}{:06d}".format(j,k)))
I = lambda: list(map(int, input().split()))
n, m = I()
a = [[i] + I() for i in range(m)]
a = sorted(a, key=lambda x: (x[1], x[2]))
b = []
j0 = 0
p = 1
for i, j, k in a:
    if j != j0:
        p = 1
    else:
        p += 1
    b.append([i, j, p])
    j0 = j
b = sorted(b, key=lambda x: x[0])
for i, j, k in b:
    print(("{:06d}{:06d}".format(j, k)))

I = lambda: list(map(int, input().split()))
n, m = I()
a = [[i] + I() for i in range(m)]
a = sorted(a, key=lambda x: (x[1], x[2]))
b = []
j0 = 0
p = 1
for i, j, k in a:
    p = 1 if j != j0 else p + 1
    b.append([i, j, p])
    j0 = j
for i, j, k in sorted(b):
    print(("{:06d}{:06d}".format(j, k)))

-    if j != j0: -        p = 1 -    else: -        p += 1 +    p = 1 if j != j0 else p + 1 -b = sorted(b, key=lambda x: x[0]) -for i, j, k in b: +for i, j, k in sorted(b):