prefectures = Hash.new {|h, k| h[k] = []}

n, m = gets.split.map(&:to_i)
m.times do |i|
  p, y = gets.split.map(&:to_i)
  prefectures[p] << [y, i]
end

puts prefectures.flat_map {|k, v|
  v.sort.map.with_index(1) {|(y, i), j| [i, sprintf("%06d%06d", k, j)]}
}.sort.map(&:last)