Eye of the Storm
暂无测试数据。
云浅来到了风暴的中心。这里漂浮着一个长为 $n$ 的，由小写字母组成的字符串 $S$。字符串的下标从 $1$ 开始。
想要逃出风暴，就需要回答一些询问。
每次询问会给出一对正整数 $l,r$ 和一个字符串 $T$，云浅需要回答 $S_{l\cdots r}$ 这段子串内有多少个子序列是 $T$。这里保证 $T$ 的长度为 $2$。
形式化地，你需要求出有多少对 $(i,j)$ 满足 $l\le i<j\le r$，使得 $S_i=T_1,S_j=T_2$。
现在云浅预测出了风暴在接下来 $q$ 个时刻内的询问，你需要帮她求出每个询问的答案。
输入格式
第一行两个正整数 $n,q$。
第二行一个长为 $n$ 的字符串 $S$。
接下来 $q$ 行，每行会给出两个正整数 $l,r$ 和一个字符串 $T$，表示云浅需要回答的询问。保证 $|T|=2$。
输出格式
对于每次询问，输出一行一个正整数表示答案。
数据范围
对于 $100\%$ 的数据，$1\le n,q\le 2\times 10^5,1\le l\le r\le n,S,T$ 中只含小写英文字母，$|T|=2$。
| 测试点编号 | $n$ | $q$ | 其他 |
|---|---|---|---|
| $1\sim 4$ | $\le 100$ | $\le 100$ | 无 |
| $5\sim 8$ | $\le 5000$ | $\le 5000$ | 无 |
| $9\sim 10$ | $\le 10^5$ | $\le 10^5$ | 所有的 $S_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$ | 无 |
10 4
yunqianqwq
2 7 un
3 9 qw
4 10 wq
2 10 nq
2
2
1
5
13 3
todayissunday
4 10 sn
2 13 ay
1 12 od
2
3
2