D. 风暴之眼

云浅来到了风暴的中心。这里漂浮着一个长为 n 的，由小写字母组成的字符串 S。字符串的下标从 1 开始。

想要逃出风暴，就需要回答一些询问。

每次询问会给出一对正整数 l,r 和一个字符串 T，云浅需要回答 这段子串内有多少个子序列是 T。这里保证 T 的长度为 2。

形式化地，你需要求出有多少对 (i,j) 满足 ，使得 。 ​ 现在云浅预测出了风暴在接下来 q 个时刻内的询问，你需要帮她求出每个询问的答案。

第一行两个正整数 n,q。

第二行一个长为 n 的字符串 S。

接下来 q 行，每行会给出两个正整数 l,r 和一个字符串 T，表示云浅需要回答的询问。保证 |T|=2。

对于每次询问，输出一行一个正整数表示答案。

样例输入1

10 4
yunqianqwq
2 7 un
3 9 qw
4 10 wq
2 10 nq

样例输出1

2
2
1
5

样例解释1

对于第一次询问，符合条件的 (i,j) 分别为 (2,3),(2,7)。

对于第二次询问，符合条件的 (i,j) 分别为 (4,9),(8,9)。

对于第三次询问，符合条件的 (i,j) 只有一个，即 (9,10)。

对于第四次询问，符合条件的 (i,j) 分别为 (3,4),(3,8),(3,10),(7,8),(7,10)。

样例输入2

13 3
todayissunday
4 10 sn
2 13 ay
1 12 od

样例输出2

2
3
2

样例解释2

对于第一次询问，符合条件的 (i,j) 分别为 (7,10),(8,10)。

对于第二次询问，符合条件的 (i,j) 分别为 (4,5),(4,13),(12,13)。

对于第三次询问，符合条件的 (i,j) 分别为 (2,3),(2,11)。

对于 100% 的数据，中只含小写英文字母，|T|=2。