N, M = gets.split.map(&:to_i)
pys = M.times.map { gets.split.map(&:to_i) }.sort_by { |p, y| [p, y] }
number = Array.new
l = 1
r = 1
pys.each_with_index do |py, i|
  unless i == 0
    r = l == py[0] ? r + 1 : 1
    l = l == py[0] ? l : l + 1
  end
  puts l.to_s.rjust(6, "0") + r.to_s.rjust(6, "0")
end