n_pref, n_city = gets.chomp.split.map(&:to_i)
cities = []
n_city.times{cities << gets.chomp.split.map(&:to_i)}

h = {}
pref = Array.new(n_pref + 1, 0)
cities.sort_by{|p, y| y}.each{|p, y|
    pref[p] += 1
    h[[p, y]] = "#{sprintf("%06d", p)}#{sprintf("%06d", pref[p])}"
}
cities.each{|city| puts "#{h[city]}"}