n_pref, n_city = gets.chomp.split.map(&:to_i)
cities = []
pref = Array.new(n_pref + 1){[]}
n_city.times{
    p, y = gets.chomp.split.map(&:to_i)
    pref[p] << y
    cities << [p, y]
}
pref.each{|arr| arr.sort!}
cities.each{|city| puts "#{sprintf("%06d", city[0])}#{sprintf("%06d", pref[city[0]].index(city[1]) + 1)}"}
