(N, M) = gets.split(/ /).map(&:to_i)
obj = []
M.times do |r|
  (_p, _y) = gets.split(/ /).map(&:to_i)
  obj << {r: r, p: _p, y: _y}
end
obj.sort_by! do |o|
  [o[:p], o[:y]]
end
current = nil
c = 1
obj.each do |o|
  if current.nil?
    current = o[:p]
  end
  if current != o[:p]
    current = o[:p]
    c = 1
  end

  o[:code] = format('%06d%06d', current, c)
  c += 1
end
obj.sort_by! do |o|
  o[:r]
end
obj.each do |o|
  puts o[:code]
end

