local zones = io.read("*n")
local num = io.read("*n")
local data = {}
for j = 1,num do
	local idx = io.read("*n")
	local y = io.read("*n")
	local d = {n = 0, year = y,i=j,z = idx}
	table.insert(data,d)
end
local tmp = {}
table.sort(data,function(a,b)
 	return a.year < b.year
end)

-- for k,v in ipairs(data) do
-- 	v.k = k
-- end
for k,v in ipairs(data) do
	if not tmp[v.z] then
		tmp[v.z] = 1
	else
		tmp[v.z] = tmp[v.z] + 1
	end
	v.n = tmp[v.z]
end

local x = {}
for k,v in pairs(data) do
	x[v.i]={v.z,v.n}
end

for i = 1,#x do
	local digits = 0
	if x[i][1] < 100000 then
		local num = x[i][1]

		for i= 1,5 do
			num = num/10
			if num >= 10 then
				digits = digits + 1
			end
		end
	end
	x[i][1] = string.rep("0",5-digits)..x[i][1]
	if x[i][2] < 100000 then
		local num = x[i][2]
		for i= 1,5 do
			num = num/10
			if num >= 10 then
				digits = digits + 1
			end
		end
	end
	x[i][2] = string.rep("0",5-digits)..x[i][2]
	print(x[i][1]..x[i][2])
end