# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def _cal(preSum, count):
    if preSum[0] > count[0]:
        return 1
    elif preSum[1] > count[1]:
        return 2
    elif preSum[2] > count[2]:
        return 3
    else:
        return 4


def solution(S, P, Q):
    # write your code in Python 3.6
    d = {'A':0, 'C':1, 'G':2, 'T':3}
    preSum = [[0, 0, 0, 0] for _ in range(len(S))]
    for i, s in enumerate(S):
        preSum[i] = preSum[i-1][:]
        preSum[i][d[s]] += 1
    result = [0] * len(P)
    for i in range(len(P)):
        x, y = P[i], Q[i]
        if x == 0:
            count = [0, 0, 0, 0]
        else:
            count = preSum[x-1]
        result[i] = _cal(preSum[y], count)
    return result