n, m = gets.split.map(&:to_i)

cities = []
m.times do |i|
  q, y = gets.split.map(&:to_i)
  cities << [y, q, i]
end

cities.sort_by! {|elm| elm[0] }

prefs = Array.new(n+1, 0)

cities.map {|c|
  city_code = (prefs[c[1]] += 1)
  [c[2], sprintf("%06d%06d", c[1], city_code)]
}.sort_by! {|elm| elm[0]}.each do |c|
  puts c[1]
end
