N, M = gets.split.map(&:to_i)
P = Array.new(M)
Y = Array.new(M)
M.times do |i|
  P[i], Y[i] = gets.split.map(&:to_i)
end

p_hash = Hash.new{|hash, key| hash[key] = []}
left_hash = Hash.new()
P.each_with_index do |p_num, i|
  p_hash[p_num] << Y[i]
  left_hash[p_num] = p_num.to_s.rjust(6, "0")
end

p_hash.each {|key, ary| ary.sort!}

number = Array.new(M)
M.times do |i|
  leftStr = left_hash[P[i]]
  idx = p_hash[P[i]].index(Y[i]) + 1
  rightStr = idx.to_s.rjust(6, "0")
  number[i] = leftStr + rightStr
  puts number[i]
end
