该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

徐老师自从上回修好了羊腿复制器以后，家里的羊腿多到快放不下啦！

于是他决定拿出一部分出来卖，这里为了方便出售，徐老师将所有羊腿分了 $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 bc

4
3
9