알파벳 소문자로만 이루어진 문자열 S가 주어집니다.

이 문자열에 대해 특정 구간 [L, R] 사이에 특정 알파벳이 몇 번 등장하는지 묻는 질문(쿼리)이 수시로 들어옵니다.

질문이 들어올 때마다 각 구간에 해당 알파벳이 등장하는 횟수를 빠르게 구해 출력하는 프로그램을 작성하시오.

(단, 문자열의 인덱스는 0부터 시작합니다.)

입력

첫째 줄에 알파벳 소문자로만 구성된 문자열 S가 주어집니다. (1 ≤ 문자열의 길이 ≤ 100,000)

둘째 줄에 질문의 개수 Q가 주어집니다. (1 ≤ Q ≤ 100,000)

셋째 줄부터 Q개의 줄에 걸쳐 찾으려는 알파벳 소문자 alpha와 구간의 시작 인덱스 L, 끝 인덱스 R이 공백으로 구분되어 한 줄에 하나씩 주어집니다. (0 ≤ L ≤ R < 문자열의 길이)

출력

질문이 들어온 순서대로, 각 질문에 대한 답(해당 알파벳의 등장 횟수)을 한 줄에 하나씩 차례대로 출력합니다.

예제 입력 1

banana
3
a 1 5
n 0 3
b 2 4

예제 출력 1

3
1
0

힌트 (예제 설명)

문자열은 S = "banana" 입니다. (길이 6, 인덱스 0~5)

• 1번째 질문: 'a'가 1번부터 5번 인덱스("anana") 사이에 몇 번 나오는가? -> 1번, 3번, 5번 인덱스에 'a'가 총 3번 등장하므로 3입니다.
• 2번째 질문: 'n'이 0번부터 3번 인덱스("bana") 사이에 몇 번 나오는가? -> 2번 인덱스에 'n'이 1번 등장하므로 1입니다.
• 3번째 질문: 'b'가 2번부터 4번 인덱스("nan") 사이에 몇 번 나오는가? -> 'b'는 0번 인덱스에만 있고 해당 범위 내에는 없으므로 0입니다.