N,M=gets.split.map(&:to_i)
P=[]
for i in 1..M
	P<<gets.split.map(&:to_i)
end
Q=Array.new(N).map{[]}
P.each{|e|
	Q[e[0]-1]<<e[1]
}
Q.each{|e|
	e.sort!
}
P.each{|e|
	puts ("%06d"%e[0].to_s)+("%06d"%(Q[e[0]-1].index(e[1])+1).to_s)
}