
local insert = table.insert
local n, m = io.read('*n', '*n')
local ret = {}
for i = 1, m do
	local p, y = io.read('*n', '*n')
	ret[p] = ret[p] or {}
	insert(ret[p], {idx = i, val = y})
end
local ans = {}
for i, v in pairs(ret) do
	table.sort(v, function(a, b)
		return a.val < b.val
	end)
	for j, vv in ipairs(v) do
		ans[vv.idx] = string.format("%06d%06d", i, j)
	end
end
for i = 1, m do
	print(ans[i])
end
