n,m = gets.split.map(&:to_i)
detail = []
m.times do |i|
  detail << gets.chomp.split.map(&:to_i)
  detail[i].push(i,nil)
end

s_det = detail.sort

id = 1
m.times do |i|
  if s_det[i+1] == nil && s_det[i-1][0] == s_det[i][0]
    s_det[i][3] = id
    break
  elsif s_det[i+1] == nil && s_det[i-1][0] != s_det[i][0]
    s_det[i][3] = 1
  elsif s_det[i][0] == s_det[i+1][0]
    s_det[i][3] = id
    id += 1
  else
    s_det[i][3] = id
    id = 1
  end
end

det = s_det.sort_by{|a| a[2]}

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