# 2018-11-04
# ABC113 C
# Your code here
N,M =gets.strip.split.map(&:to_i)
data = M.times.map{ gets.strip.split.map(&:to_i) }

datasort = []
datanew = Array.new(N,[])
num　= Array.new(N,1)

# print data
(0..N-1).each do |i|
(0..M-1).each do |j|
  # print data[j][0]
  if data[j][0] == i + 1
    datasort << data[j][1]
  end
end
 datasort = datasort.sort
 #num = 0
 # print datasort
 k=0
 (0..M-1).each do |j|
   if data[j][0] == i + 1
    datasort.each do |num|
      if data[j][1] == num
        datanew[j] = [i + 1,k + 1]
      end
    k += 1
    end
  k=0
   end
 end
 datasort = []
 end

# print datanew

(0..M-1).each do |i|
  print "%06d" %  datanew[i][0]
  print "%06d" %  datanew[i][1]
  print "\n"
end
