class Heap
  attr_reader :size

  def initialize
    @heap = []
    @data = {}
    @size = 0
  end

  def add(n, data)
    i = @size
    while i > 0 do
      parent_index = (i - 1) / 2
      break if n >= @heap[parent_index]

      @heap[i] = @heap[parent_index]
      i = parent_index
    end

    @heap[i] = n
    @data[n] = data.merge(key: n)
    @size += 1
  end

  def pop
    min_n = @heap[0]
    @size -= 1
    n = @heap[@size]
    i = 0
    while i * 2 + 1 < @size do
      child_index1 = i * 2 + 1
      child_index2 = i * 2 + 2
      if child_index2 < @size && @heap[child_index2] < @heap[child_index1]
        child_index1 = child_index2
      end
      break if @heap[child_index1] >= n

      @heap[i] = @heap[child_index1]
      i = child_index1
    end
    @heap[i] = n
    @data.delete(min_n)
  end

  def min; @heap[0] end
  def values; @heap.first(@size) end
  def inspect; "Heap: #{values}" end
end

N, M = gets.split.map(&:to_i)
heaps = {}
cities = []
M.times do |i|
  pref, year = gets.split.map(&:to_i)
  heaps[pref] ||= Heap.new
  heaps[pref].add(year, {n: i})
  cities[i] = {p: pref}
end

# p heaps
heaps.each do |pref, heap|
  o = 1
  while c = heap.pop
    cities[c[:n]][:o] = o
    o += 1
  end
end

cities.each do |city|
  puts "%06d%06d" % [city[:p], city[:o]]
end