N, M = gets.split.map(&:to_i)

cities = []

cities_n = []

ids = []


M.times do |i|
  p, y = gets.split.map(&:to_i)
  cities.push([p, y, i])
end

cities.sort!{|a, b| a[1] <=> b[1]}


cities.each do |i|
  p_ = i[0]
    
  if(cities_n[p_].nil?)
    cities_n[p_] = 1
  else
    cities_n[p_] += 1
  end
  
  n = cities_n[p_]

  id1 = p_.to_s.rjust(6,'0')
         
  id2 = n.to_s.rjust(6,'0')

  id = id1.to_s + id2.to_s
  
  ids.push([id, i[2]])

end

ids.sort!{|a, b| a[1] <=> b[1]}

ids.each do |i|
  puts i[0]
end

