def factorize = { long target -> 
 
    if (target == 1) return [1L]
 
    if (target < 4) return [1L, target]
 
    def targetSqrt = Math.sqrt(target)
    def lowfactors = (2L..targetSqrt).findAll { (target % it) == 0 }
    if (lowfactors == []) return [1L, target]
    def nhalf = lowfactors.size() - ((lowfactors[-1]**2 == target) ? 1 : 0)
 
    [1] + lowfactors + (0..<nhalf).collect { target.intdiv(lowfactors[it]) }.reverse() + [target]
}
 
def decomposePrimes = { target ->
    def factors = factorize(target) - [1]
    def primeFactors = []
    factors.eachWithIndex { f, i ->
        if (i==0 || factors[0..<i].every {f % it != 0}) {
            primeFactors << f
            def pfPower = f*f
            while (target % pfPower == 0) {
                primeFactors << f
                pfPower *= f
            }
        }
    }
    primeFactors
}
 

ZGVmIGZhY3Rvcml6ZSA9IHsgbG9uZyB0YXJnZXQgLT4gCiAKICAgIGlmICh0YXJnZXQgPT0gMSkgcmV0dXJuIFsxTF0KIAogICAgaWYgKHRhcmdldCA8IDQpIHJldHVybiBbMUwsIHRhcmdldF0KIAogICAgZGVmIHRhcmdldFNxcnQgPSBNYXRoLnNxcnQodGFyZ2V0KQogICAgZGVmIGxvd2ZhY3RvcnMgPSAoMkwuLnRhcmdldFNxcnQpLmZpbmRBbGwgeyAodGFyZ2V0ICUgaXQpID09IDAgfQogICAgaWYgKGxvd2ZhY3RvcnMgPT0gW10pIHJldHVybiBbMUwsIHRhcmdldF0KICAgIGRlZiBuaGFsZiA9IGxvd2ZhY3RvcnMuc2l6ZSgpIC0gKChsb3dmYWN0b3JzWy0xXSoqMiA9PSB0YXJnZXQpID8gMSA6IDApCiAKICAgIFsxXSArIGxvd2ZhY3RvcnMgKyAoMC4uPG5oYWxmKS5jb2xsZWN0IHsgdGFyZ2V0LmludGRpdihsb3dmYWN0b3JzW2l0XSkgfS5yZXZlcnNlKCkgKyBbdGFyZ2V0XQp9CiAKZGVmIGRlY29tcG9zZVByaW1lcyA9IHsgdGFyZ2V0IC0+CiAgICBkZWYgZmFjdG9ycyA9IGZhY3Rvcml6ZSh0YXJnZXQpIC0gWzFdCiAgICBkZWYgcHJpbWVGYWN0b3JzID0gW10KICAgIGZhY3RvcnMuZWFjaFdpdGhJbmRleCB7IGYsIGkgLT4KICAgICAgICBpZiAoaT09MCB8fCBmYWN0b3JzWzAuLjxpXS5ldmVyeSB7ZiAlIGl0ICE9IDB9KSB7CiAgICAgICAgICAgIHByaW1lRmFjdG9ycyA8PCBmCiAgICAgICAgICAgIGRlZiBwZlBvd2VyID0gZipmCiAgICAgICAgICAgIHdoaWxlICh0YXJnZXQgJSBwZlBvd2VyID09IDApIHsKICAgICAgICAgICAgICAgIHByaW1lRmFjdG9ycyA8PCBmCiAgICAgICAgICAgICAgICBwZlBvd2VyICo9IGYKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHByaW1lRmFjdG9ycwp9Cg==