N,M=gets.chomp.split(" ").map(&:to_i)
p = []
y = []
arr = []
(1..M).each do |i|
  p[i], y[i] = gets.chomp.split(" ").map(&:to_i)
  if arr[p[i]].nil?
    arr[p[i]] = [{index: i, value: y[i]}]
  else
    arr[p[i]].push({index: i, value: y[i]})
  end
end
code_arr = []
arr[1..N].each.with_index(1) do |v, i|
  next if v.nil?
  res = v.sort_by{|vv| vv[:value]}
  res.each.with_index(1) do |vv, rank|
    ind = arr[i].find{|vvv| vvv[:value] == vv[:value] }[:index]
    code_arr[ind] = p[ind].to_s.rjust(6, '0') + rank.to_s.rjust(6, '0')
  end
end
code_arr.each do |c|
  print("#{c}\n")
end