n,m = gets.split.map(&:to_i)
pref = Array.new(n+1){[]}
ans = Array.new(m,nil)
m.times do |i|
  pi,yi = gets.split.map(&:to_i)
  pref[pi] << [i,yi]
end
pref.each_with_index do |arr,j|
  arr.sort_by!{|a| a[1]}
  arr.each_with_index do |a,i|
    ans[a[0]] = "%06d" % j  + "%06d" % (i+1)
  end
end

ans.each do |s|
  puts s
end
