local N, M = io.read("n", "n")
local cities = {}
local prefs = {}
for i=1,M do
     local p, y = io.read("n", "n")
     local c = {i, p, y, -1}
     if not prefs[p] then
         prefs[p] = {}
     end
     table.insert(prefs[p], c)
     table.insert(cities, c)
end
for k, v in pairs(prefs) do
    table.sort(v, function(x1, x2)
        return x1[3] < x2[3]
    end)
    for kk, vv in ipairs(v) do
        local ci = vv[1]
        cities[ci][4] = kk
    end
end

for i=1,M do
    local c = cities[i]
    local p = c[2]
    local x = c[4]
    print(string.format("%06d%06d", p, x))
end

