N, M = gets.split.map(&:to_i)
lists = []
pre = {}
M.times do
  s, t = gets.chomp.split
  t = t.to_i
  lists << [s, t]
  (pre[s] ||= []) << t
end

# p lists
pre.each do |k, v|
  v.sort_by!{|x|x}
end
# p pre
lists.each do |list|
  ind = pre[list[0]].bsearch_index{|x|x >= list[1]} + 1
  puts"#{list[0].rjust(6, "0")}#{ind.to_s.rjust(6, "0")}"
end