n,m=gets.chomp.split.map(&:to_i)
d=[]
for i in 1..m do
  d<<gets.chomp.split.map(&:to_i)+[i]
end
d.sort!
ans=[]
tmp=[0,0]
for ary in d do
  if tmp[0]!=ary[0] then
    tmp[0]=ary[0]
    tmp[1]=0
  end
  tmp[1]+=1
  str="0"*(6-ary[0].digits.length)+ary[0].to_s+"0"*(6-tmp[1].digits.length)+tmp[1].to_s
  ans[ary[2]]=str
end
ans.each do |v|
  puts v
end