def gs() STDIN.gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end
 
def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end


n,m = gsmi
pyis = Array.new(m) do |i|
	p,y = gsmi
	[p,y,i]
end

now = 0
j = 0
ss = []

pyis.sort.each do |pyi|
	if now == pyi[0]
		j += 1
	else
		now = pyi[0]
		j = 1
	end
	ss << [pyi[2],sprintf("%06d%06d", pyi[0], j)]
end

ss.sort.each{|s| puts s[1]}
