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

prefs = Array.new(m)

m.times do |i|
  p, y = gets.chomp.split.map(&:to_i)
  prefs[i] = {index: i+1, p: p, y: y, id: ''}
end

prefs.group_by{|pref| pref[:p]}.each do |pr, group|
  group.sort_by{|pref| pref[:y]}.each_with_index do |pref, j|
    pref[:id] = format('%06d', pr) + format('%06d', j+1)
  end
end

prefs.sort_by{|pref| pref[:index]}.each do |pref|
  puts pref[:id]
end
