_=gets.chomp.split(" ").map(&:to_i)
ys,ls={},[]
while l=gets
  next if l.chomp == ""
  p,y=l.chomp.split(" ").map(&:to_i)
  ls<<{y: y, p: p.to_s}
  (ys[p] ||= []) << y
end
ys.each_pair{|_,v|v.sort! if v.length > 1 }
ls.each do |x|
  puts [x[:p],ys[x[:p].to_i].bsearch_index{|yy|x[:y]<=yy}.next.to_s].map{|z|z.rjust(6,?0)}.join
end