题目描述

给定长度为 n 的小写字母字符串 s。回答 m 次查询，每次给出 l、r 和字母 c，求子串 s[l..r] 中 c 的出现次数。

输入格式

第一行包含 n、m。第二行包含长度恰为 n 的字符串 s。接下来 m 行每行包含 l、r、c，保证 1 <= l <= r <= n。

输出格式

每次查询输出一行答案。

样例

8 4
abacabad
1 8 a
2 5 b
3 7 a
4 4 d

4
1
3
0

数据范围

• 对于 30% 的数据，1 <= n,m <= 100；
• 对于 50% 的数据，1 <= n,m <= 1000；
• 对于 100% 的数据，1 <= n,m <= 200000；
• s 仅包含小写字母。