n, m = gets.split.map(&:to_i)
py = Array.new(m){gets.split.map(&:to_i)}
sorted = py.sort
ps = Array.new(n){[]}
hash = Hash.new{|h,k| h[k]={}}

sorted.each do |ary|
  ps[ary[0]-1] << ary[1]
end

ps.each_with_index do |ary, i|
  ary.each_with_index do |year, j|
    hash[i+1][year] = (i+1).to_s.rjust(6,"0") + (j+1).to_s.rjust(6,"0")
  end
end

py.each do |ary|
  puts hash[ary[0]][ary[1]]
end