n, m = gets.split.map(&:to_i)
p, y = Array.new(m) { gets.split.map(&:to_i) }.transpose
h = Hash.new(0)
ret = {}

p.zip(y).sort.each do |p, y|
  h[p] += 1
  ret[y] = format('%06d', p) + format('%06d', h[p])
end

y.each { |e| puts ret[e] }