n, m = gets.split.map(&:to_i)
prefs = n.times.map{Array.new()}
city_by_year = {}
city_by_index = []
m.times do |i|
  p, y = gets.split.map(&:to_i)
  city_by_year[y] = [p]
  city_by_index << y
  prefs[p - 1] << y
end


prefs.each_with_index do |cities, i|
  cities.sort.each_with_index do |year, j|
    city_by_year[year] << j
  end
end
city_by_index.each do |y|
  printf("%06d%06d\n", city_by_year[y][0], city_by_year[y][1] + 1)
end
