local sheng = io.read("*n")
local shi = io.read("*n")

local tab = {}
local tab1 = {}
local t = {}

for i=1,shi do
	local s1 = io.read("*n")
	local s2 = io.read("*n")
	if not tab[s1] then
		tab[s1] = {}
	end
	table.insert(tab[s1], {s1, s2, i})
	tab1[s1] = true
end

for v,_ in pairs(tab1) do
	table.sort(tab[v], function(a,b)
		return a[2] < b[2]
	end)
	for i,v in ipairs(tab[v]) do
		t[v[3]] = string.format("%06d%06d", v[1], i)
	end
end

for i,v in ipairs(t) do
	print(v)
end