local n,m=io.read("n","n")
local city={}
for i=1,m do
    local p,y=io.read("n","n")
    city[i]={p,y,i}
end

table.sort(city,function(x,y)
    if x[1]~=y[1] then
        return x[1]<y[1]
    else
        return x[2]<y[2]
    end
end)

local id={}
local x=1
local P=0
for i=1,m do
    local p=city[i][1]
    local y=city[i][2]
    local c=city[i][3]
    if P==p then
        x=x+1
    else
        x=1
    end
    id[c]=string.format("%06d",p)..string.format("%06d",x)
    P=p
end

for i=1,m do
    print(id[i])
end