N,M = gets.split.map(&:to_f)
prefs = Hash[(1..N).map{ |n| [n, []] }]
Cities = (0...M).map{
  p,y = gets.split.map(&:to_i)
  prefs[p] << y
  [p,y]
}

years = Hash[prefs.map{ |n,ys| 
  [n, Hash[ys.sort.map.with_index{ |y,k| [y,k+1] }]]
}]

Cities.each{ |p,y|
  puts sprintf("%06d%06d", p, years[p][y])
}