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