=begin
N M
P1 Y1
...
Pn Yn
=end

n, m = gets.chomp.split(" ").map(&:to_i)
pys = m.times.map do
  gets.chomp.split(" ").map(&:to_i)
end

pys_ordered = pys.sort_by do |p, y|
  y
end

prefectures = {}
results = {}

pys_ordered.each do |p, y|
  prefectures[p] ||= 0
  current = (prefectures[p] += 1)

  results[[p, y]] = sprintf("%06d%06d", p, current)
end

pys.each do |py|
  puts results[py]
end
