n, m = gets.split.map(&:to_i)
p = []
h = Hash.new(0);
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
  h[y[0]] +=1
end
p.sort! {|a, b| b[1][1]<=>a[1][1]}
m.times do |i|
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(h[p[i][1][0]].to_s.rjust(6, "0"))
  h[p[i][1][0]] -= 1
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end