题目描述

方老师的仓鼠越养越多，有次偶然的机会被谢校长知道了，具备商业头脑的校长就去跟方老师商量，准备拿出一部分仓鼠进行销售。谢老师看了方老师的仓鼠后，想到了一个好主意，他把仓鼠按照可爱程度分成了26个等级，分别用26个小写字母进行表示。方老师不舍的取出了n只仓鼠，给它们编上序号分别为1～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只仓鼠和谢校长会提出的问题

第二行包含一个长度为n的字符串a，分别表示n只仓鼠的可爱程度

接下来m行，每行两个整数l，r和一个长度为2的字符串，表示谢校长的一次询问

输出格式

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

数据范围

对于100%的数据，$1 \le n , m \le 2 * 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