N, M = gets.split.map(&:to_i)
Ps = Hash.new{|hash, key| hash[key] = []}
Query = Array.new()
M.times do |i|
  a, b = gets.split.map(&:to_i)
  Ps[a] = Ps[a].push(b)
  Query.push([a,b])
end

ans_table = Hash.new()
Ps.each do |key,value|
  value.sort!
  value.each_with_index{|y, i|
     ans_table[[key,y]] = format('%06d', key) + format('%06d', i+1)
  }
end

Query.each{|x|
  puts ans_table[x]
}
