bwt

local markChar = "\254"

function encode(s)
    local s = s..markChar
    local rotations = {}
    for i=1,#s do
        s = string.sub(s,#s)..string.sub(s,1,#s-1)
        print(i..": "..string.sub(s,1,10))
        rotations[i] = s
    end
    table.sort(rotations)
    local returnValue = ""
    for i=1,#rotations do
        returnValue = returnValue..string.sub(rotations[i],#rotations[i])
        coroutine.yield()
    end
    return returnValue
end

function decode(s)
    local t = {}
    for k=1,#s do
        for i=1,#s do
            local char = string.sub(s,i,i)
            t[i] = not t[i] and char or char .. t[i]
            coroutine.yield()
        end
        table.sort(t)
    end
    for i=1,#t do
        if (string.sub(t[i],#t[i]) == markChar) then
            return string.sub(t[i],1,#t[i]-1)
        end
    end
end