N, M = gets.split.map(&:to_i)

s = []

# p s

M.times do |i|
  
  p, y = gets.split.map(&:to_i)
  s.push([p, y, i+1, nil])
  
end

ns = s.sort_by do |b|
  [b[0], b[1], b[2], b[3]]
end

t = 1
ns[0][3] = 1
1.upto(M-1) do |i|
  
  t = 0 if ns[i][0] != ns[i-1][0]
  t += 1
  ns[i][3] = t
end

ns = ns.sort_by do |b|
  b[2]
end

# p ns 

ns.each do |k|
  
  puts k[0].to_s.rjust(6,?0) + k[3].to_s.rjust(6,?0)

end

  
  
  
