val String.prefixSumOfGenoms: Array<IntArray>
    get() {
        val genoms = Array(3) {
            IntArray(length+1)
        }

        for(i in 0 until length) {
            var (a, c, g) = arrayOf<Short>(0, 0, 0)
            when(this[i]) {
                'A' -> {a = 1}
                'C' -> {c = 1}
                'G' -> {g = 1}
            }
            genoms[0][i+1] = genoms[0][i] + a
            genoms[1][i+1] = genoms[1][i] + c
            genoms[2][i+1] = genoms[2][i] + g
        }

        return genoms
    }

fun Array<IntArray>.getMinImpact(startIndex: Int, endIndex: Int): Int  {
    var impact = 4
    run loop@{
        forEachIndexed { index, genoms ->
            if (genoms[endIndex] - genoms[startIndex] > 0) {
                impact = index + 1
                return@loop
            }
        }
    }
    return impact
}

fun solution(S: String, P: IntArray, Q: IntArray): IntArray{
    val genoms = S.prefixSumOfGenoms
    val result = IntArray(P.size)
    for(i in 0 until P.size)
        result[i] = genoms.getMinImpact(P[i], Q[i]+1)
    return result
}