n, m = gets.to_s.split.map{|t|t.to_i}
pys  = Array.new(m){ gets.to_s.split.map{|t|t.to_i} }

pys.sort!

used = Array.new(n+1){ false }

id = -1
pys.each do |prefecture, y|
  
  if !used[prefecture]
    id = 0
    used[prefecture] = true
  end
  
  id += 1
  
  puts prefecture.to_s.rjust(6, '0') + id.to_s.rjust(6, '0')
end