인간-컴퓨터 상호작용

• 부분합 쿼리 문제. 알파벳별로 누적합을 각각 만들어주고 쿼리에서 물어보는 알파벳의 누적합에서 계산해주면 된다.
• 누적합을 최대 26개 만들어야 하니까 O(|S|*26)이 걸리고, 쿼리는 각 쿼리당 O(1) 에 처리가능하다. 알파벳의 갯수 26을 상수로 보면, O(|S| + q).

"""Solution code for "BOJ 16139. 인간-컴퓨터 상호작용".

- Problem link: https://www.acmicpc.net/problem/16139
- Solution link: http://www.teferi.net/ps/problems/boj/16139

Tags: [Prefix sum]
"""

import sys


def main():
    S = sys.stdin.readline().rstrip()
    prefix_sums = {}
    for c in set(S):
        prefix_sums[c] = ([ps := 0] +
                          [ps := (ps + 1 if c == s_i else ps) for s_i in S])
    q = int(sys.stdin.readline())
    for _ in range(q):
        alpha, l, r = sys.stdin.readline().split()
        try:
            psum = prefix_sums[alpha]
            print(psum[int(r) + 1] - psum[int(l)])
        except KeyError:
            print('0')



if __name__ == '__main__':
    main()