N, M = gets.split.map(&:to_i)
arr = []
M.times do |i|
  p, y = gets.split.map(&:to_i)
  arr << [p, y]
end
(1..N).each do |i|
  arr.select{ |a| a[0] == i }.sort_by{ |b| b[1] }.each_with_index do |v, count|
    arr[arr.index(v)] << count + 1
  end
end
arr.each do |v|
  puts "#{"%06d"%v[0]}#{"%06d"%v[2]}"
end
