STX = 
ETX = 

def bwt(s)
    for c in s.split('')
        if c == STX or c == ETX then
            raise ArgumentError.new()
        end
    end

    ss = ( % [STX, s, ETX]).split('')
    table = []
    for i in 0 .. ss.length - 1
        table.append(ss.join)
        ss = ss.rotate(-1)
    end

    table = table.sort
    return table.map{ |e| e[-1] }.join
end

def ibwt(r)
    len = r.length
    table = [] * len
    for i in 0 .. len - 1
        for j in 0 .. len - 1
            table[j] = r[j] + table[j]
        end
        table = table.sort
    end
    for row in table
        if row[-1] == ETX then
            return row[1 .. -2]
        end
    end
    return 
end

def makePrintable(s)
    s = s.gsub(STX, )
    return s.gsub(ETX, )
end

def main
    tests = [
        ,
        ,
        ,
        ,
        ,
        
    ]
    for test in tests
        print makePrintable(test), 
        print 

        begin
            t = bwt(test)
            print makePrintable(t), 

            r = ibwt(t)
            print , r, 
        rescue ArgumentError => e
            print e.message, 
            print 
        end
    end
end

main()