n, m = STDIN.gets.split(" ").map(&:to_i)

cities = Array.new(n) do [] end
pys = []
for i in 0...m
  p, y = STDIN.gets.split(" ").map(&:to_i)
  p -= 1
  pys << [p,y]
  cities[p] << y
end

cities = cities.map{|years|
  Hash[years.sort.each_with_index.to_a]
}

for p, y in pys
  puts("%06d%06d" % [p+1, cities[p][y]+1])
end
