g=proc{gets.split.map &:to_i};n, m = g.call;z = n + 1;states = [];z.times { states << [] };w = [];
m.times do
  p, y = g.call;states[p] << y;w << [p, y];
end
hash = {}
z.times do |i|
  states[i].sort.each_with_index do |y, i|
    hash[y] = i + 1
  end
end
w.each do |v|
  p, y = v
  puts format('%06d%06d', p, hash[y])
end