hs=Hash.new()
hs2=Hash.new(0)
n,m=gets.split(" ").map{|e| e.to_i}
arr=[]
arr2=[]
m.times{
	a,b=gets.split(" ").map{|e| e.to_i}
	arr<<[b,a]
}
arr2=arr.sort
arr2.each{|e|
	hs2[e[1]]+=1
	hs[e]=hs2[e[1]]
}
arr.each{|e|
	a=hs[e]
	puts format('%06d%06d',e[1],a)
}