from collections import defaultdict as dd



d=dd(int)

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

l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]



o=sorted(l,key=lambda x:x[2])

for i,j in enumerate(o):

  d[j[1]]+=1

  o[i][3]=d[j[1]]



for i in sorted(o):

  print(('{0:06d}'.format(i[1])+'{0:06d}'.format(i[3])))
from collections import defaultdict as dd



d=dd(int)

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

l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]



o=sorted(l,key=lambda x:x[2])

for i,j in enumerate(o):

  d[j[1]]+=1

  o[i][3]=d[j[1]]



for i in sorted(o):

  print(("%06d%06d"%(i[1],i[3])))

from collections import defaultdict as dd

d = dd(int)
n, m = list(map(int, input().split()))
l = [[i] + list(map(int, input().split())) + [0] for i in range(m)]
o = sorted(l, key=lambda x: x[2])
for i, j in enumerate(o):
    d[j[1]] += 1
    o[i][3] = d[j[1]]
for i in sorted(o):
    print(("{0:06d}".format(i[1]) + "{0:06d}".format(i[3])))

from collections import defaultdict as dd

d = dd(int)
n, m = list(map(int, input().split()))
l = [[i] + list(map(int, input().split())) + [0] for i in range(m)]
o = sorted(l, key=lambda x: x[2])
for i, j in enumerate(o):
    d[j[1]] += 1
    o[i][3] = d[j[1]]
for i in sorted(o):
    print(("%06d%06d" % (i[1], i[3])))

-    print(("{0:06d}".format(i[1]) + "{0:06d}".format(i[3]))) +    print(("%06d%06d" % (i[1], i[3])))