说明

蒟蒻队长自从上回修好了羊腿复制器以后，家里的羊腿多到快放不下啦！

于是他决定拿出一部分出来卖，这里为了方便出售，蒟蒻队长将所有羊腿分了 $26$ 个等级，用 $26$ 个小写字母表示

现在蒟蒻队长一共拿出了 $n$ 只羊腿，编号分别为 $1 \sim n$，并且每只羊腿的品质等级为 $a_i$

在正式售卖之前，小菜菜决定考考蒟蒻队长能否快速做出反应，来提高出售效率

小菜菜将会提出 $m$ 次问题，每次询问会指向一段连续编号的羊腿，要求蒟蒻队长从中选出两只对应品质的羊腿

现在蒟蒻队长决定给小菜菜秀一把，他不但能快速拿出这两只羊腿，还能立刻告诉小菜菜他有多少种不同的选法能满足这两只羊腿，甚至选出的两只羊腿的相对顺序都是按照小菜菜的要求！

也就是说如果有这样的 $9$ 只羊腿，品质分别为 `aaabbbccc`

现在小菜菜给出的问题是在 $[2,5]$，即 `aabb` 中选出 `ab` 两只羊腿

则蒟蒻队长会给出 $4$ 种不同的方案:$(2,4),(2,5),(3,4),(3,5)$

如果小菜菜给出的询问是在 $[1,3]$，即 `aaa` 中选出 `aa` 两只羊腿

则蒟蒻队长会给出 $3$ 种不同的方案:$(1,2),(1,3),(2,3)$

现在小菜菜想知道，对于他提出的每一个询问正确答案应该是多少，以此来验证蒟蒻队长的答案是否正确

输入格式

输入第一行包含两个整数 $n,m$ 表示有 $n$ 只羊腿和小菜菜会提出 $m$ 次问题

第二行包含一个长度为 $n$ 的字符串 $a$，分别表示 $n$ 只羊腿的品质

接下来 $m$ 行，每行包含两个整数 $l,r$ 和一个长度为 $2$ 的字符串，表示小菜菜的一次提问

测试点编号	$n$	$m$	其他
$1\sim 4$	$\le 100$	$\le 100$	无
$5\sim 8$	$\le 5000$	$\le 5000$	无
$9\sim 10$	$\le 10^5$	$\le 10^5$	所有的 $a_i$ 均相同
$11\sim 12$	$\le 10^5$	$\le 3$	无
$13\sim 16$	$\le 10^5$	$\le 10^5$	无
$17\sim 20$	$\le 2\times 10^5$	$\le 2\times 10^5$	无

对于 $100\%$ 的数据，$1\le n,m \le 2\times 10^5,1\le l\le r\le n$,其中保证输入字符串只包含小写字母，且小菜菜提问的字符串长度一定为 $2$
</span>

输出格式

对于每一次提问输出一个正整数表示答案

9 3
aaabbbccc
2 5 ab
1 3 aa
1 9 bc

4
3
9

来源

CSP模拟赛