n,m=gets.split.map(&:to_i)
cities=m.times.map{|i|gets.split.map(&:to_i)<<i}
prefectures=Hash.new(0)
ans=Array.new(m)
cities.sort_by{|p,y,i|y}.each{|p,y,i|
  prefectures[p]+=1
  ans[i]="%06d%06d"%[p,prefectures[p]]
}
puts ans