# n 県数
# m 市数
n, m = gets.split.map(&:to_i)

ken = {}

data = m.times.map.with_index do |i|
  p, y = gets.split.map(&:to_i)

  ken[p] ||= []
  ken[p] << i

  [p, y]
end

ken.each do |p, value|
  value.sort! {|n| data[n].last }
  value.each.with_index do |pos, order|
    # pp [pos, order]
    data[pos][2] = order + 1
  end
end

data.each.with_index do |(p, _y, o), i|
  # puts "%06d%06d" % [p, ken[p].index(i) + 1]
  puts "%06d%06d" % [p, o]
end
