n, m = gets.split.map(&:to_i)
rets = []
ps = {}
m.times do |i|
  p, y = gets.split.map(&:to_i)
  rets.push({ p: p, y: y})
  ps[p] ||= []
  ps[p].push({ y: y, i: i })
end
ps.each do |p, v|
  sorted = v.sort{|a,b| a[:y] <=> b[:y] }
  sorted.each_with_index do |x, i|
    ret = rets[x[:i]]
    ret[:code] = ret[:p].to_s.rjust(6, '0') + (i + 1).to_s.rjust(6, '0')
  end
end
=begin
rets.map{|x| x[:p]}.uniq.each do  |p|
  sorted = rets.select{|x| x[:p] == p}.sort{|a,b| a[:y] <=> b[:y]}
  sorted.each_with_index do |x, i|
    x[:code] = x[:p].to_s.rjust(6, '0') + (i + 1).to_s.rjust(6, '0')
  end
end
=end
rets.each do |r|
  puts r[:code]
end
  