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

list = []
hash = {}
m.times.each do
  pi, yi = gets.chomp.split(' ').map(&:to_i)
  if hash.key?(pi)
    hash[pi] << yi
    hash[pi].sort!
  else
    hash[pi] = [yi]
  end
  list << [pi, yi]
end

list.each do |pi, yi|
  idx = hash[pi].find_index(yi)
  puts "#{format('%06d', pi)}#{format('%06d', idx + 1)}"
end

