index_map = {'A':100001,
'C':100001,
'G':100001,
'T':100001}

def solution(S, P, Q):
    last_location = [[len(S)-1 for i in range(len(S))] for i in range(4)]

    for index in range(len(S)-1, -1, -1):
        if S[index] == 'A':
            index_map['A'] = index
            last_location[0][index] = index_map['A']
            last_location[1][index] = index_map['C']
            last_location[2][index] = index_map['G']
            last_location[3][index] = index_map['T']
        elif S[index] == 'C':
            index_map['C'] = index
            last_location[0][index] = index_map['A']
            last_location[1][index] = index_map['C']
            last_location[2][index] = index_map['G']
            last_location[3][index] = index_map['T']

        elif S[index] == 'G':
            index_map['G'] = index
            last_location[0][index] = index_map['A']
            last_location[1][index] = index_map['C']
            last_location[2][index] = index_map['G']
            last_location[3][index] = index_map['T']
        elif S[index] == 'T':
            index_map['T'] = index
            last_location[0][index] = index_map['A']
            last_location[1][index] = index_map['C']
            last_location[2][index] = index_map['G']
            last_location[3][index] = index_map['T']

    result_list = []
    for index in range(len(P)):
        head = P[index]
        tail = Q[index]
        if last_location[0][head] <= tail:
            result_list.append(1)
        elif last_location[1][head] <= tail:
            result_list.append(2)
        elif last_location[2][head] <= tail:
            result_list.append(3)
        elif last_location[3][head] <= tail:
            result_list.append(4)

    return result_list