徐老师的羊腿出售
说明
徐老师自从上回修好了羊腿复制器以后，家里的羊腿多到快放不下啦！于是他决定拿出一部分出来卖，这里为了方便出售，徐老师将所有羊腿分了 $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$
输出格式
对于每一次提问输出一个正整数表示答案样例
9 3
aaabbbccc
2 5 ab
1 3 aa
1 9 bc4
3
9