N, M = gets.split.map &:to_i
PY = $<.map.with_index{|s, i|[*s.split.map(&:to_i), i]}
puts PY.group_by{|p, _, _| p }.map{|k, v|
  v.sort_by{|_, y, _| y }.map.with_index(1){|(_, _, i), j| ["%06d%06d"%[k, j], i] }
}.flatten(1).sort_by{|s, i| i }.map{|s, i| s }
