You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

【题目背景】

在文本处理中，经常需要统计某一段文本中特定字符或子串的出现频率。为了提高查询效率，可以预先计算前缀和数组。

【题目描述】

给定一个由小写字母组成的字符串 S，然后进行 q 次查询。每次查询给出两个整数 L 和 R（1≤L≤R≤n，其中 n 为字符串 S 的长度）以及一个小写字母 c，询问在字符串 S 的子串 S[L..R] 中，字母 c 出现的次数。

输入格式

从文件 string.in 中读入数据。

第一行一个字符串 S。

第二行一个整数 q，表示查询次数。

接下来 q 行，每行首先两个整数 L 和 R，然后一个字符 c（保证为小写字母），表示查询子串 S[L,R] 中字符 c 出现的次数。

输出格式

输出到文件 string.out。

对于每个查询，输出一行一个整数，表示该字符在子串中出现的次数。

样例输入输出

样例

aabac
3
1 3 a
2 4 b
1 5 c

2
1
1

ababa
3
1 3 a
2 4 b
1 5 c

2
2
0

样例解释

在字符串 aabac 中：

• 查询 [1,3]，子串aab 内字符 a 出现 2 次；
• 查询 [2,4] ，子串abac内字符 b 出现 1 次；
• 查询 [1,5]，子串aanac内字符 c 出现 1 次。

数据范围与提示

对于所有测试数据保证：

• 字符串长度 $n≤10^5$
• 查询次数 $q≤10^7$