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

pmym = []

m.times do
  pmym << gets.chomp.split.map(&:to_i)
end

nos = []
order = 0
pmym.each do |py|
  pref_no = py[0].to_s.rjust(6, "0")
  order = nos.select { |no| no[0] == pref_no }.count + 1
  seq_no = order.to_s.rjust(6, "0")
  nos << [pref_no, seq_no]
end
puts nos.map { |a| a.join }
