N, M = gets.chomp.split(" ").map(&:to_i)
C = Hash.new{|h, k| h[k] = []}
D = []
M.times{
  p, y = gets.chomp.split(" ").map(&:to_i)
  C[p] << y
  D << [p, y]
}

C.keys.each{|k|
  C[k].sort!
}

D.each{|p, y|
  printf("%06d%06d\n", p, C[p].bsearch_index{|x| x >= y} + 1)
}
