【题目背景】
>
万物伊始，神圣的老板娘降临人间，看着这大地鸟语花香，欣欣向荣，她很欣慰。
【题目描述】
令老板娘欣慰的是，人类终于学会了烤串串。
她来到了一个烤串摊子旁，这个摊子上从左至右依次摆放着 $n$ 个原料，原料有 $26$ 种，用 $\texttt{A}\sim\texttt{Z}$ 来表示。
老板娘是 $O$ 型血，所以她喜欢对称的烤串。她会认为一个无论是正着看还是倒着看都一样的烤串是好的。
现在给出摊子上的 $n$ 个原料，老板娘会问你 $q$ 次，如果把第 $l$ 至第 $r$ 个原料做成烤串，这个烤串会有多少个子串是好的？
【输入格式】
第一行两个整数 $n$，$type$。当 $type=1$ 时需要强制在线。
第二行一个长度为 $n$ 的字符串$s$，表示原料。
第三行一个正整数 $q$，表示询问次数。
若 $type=0$，接下来 $q$ 行，每行两个正整数 $l$、$r$，表示一次询问。
若 $type=1$，接下来 $q$ 行，每行两个正整数 $l'$、$r'$，令你上一个求得答案为 $last$（初始为 $0$），则 $l=l'\oplus last,r=r'\oplus last$，表示一次询问（$\oplus$ 即为按位异或）。
【输出格式】
$q$ 行，每行一个整数表示答案。
【输入输出样例】
样例输入 #1
5 0
CABAD
2
1 4
3 5样例输出 #1
5
3样例解释
第 $1$ 个原料到第 $4$ 个原料，为 $\texttt{CABA}$。
它的好的子串为 $\texttt{C}$、$\texttt{A}$、$\texttt{B}$、$\texttt{A}$、$\texttt{ABA}$，共 $5$ 个。
第 $3$ 个原料到第 $5$ 个原料，为 $\texttt{BAD}$。
它的好的子串为 $\texttt{B}$、$\texttt{A}$、$\texttt{D}$，共 $3$ 个。
【数据范围】
注意：本题采用捆绑测试，只有当你通过一个子任务中的所有测试点后，你才能拿到这个子任务的分数。
令 $\Sigma$ 为 $s$ 的字符集。
| 子任务 | 数据范围 | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $n,q\le97$ | 无 | $2$ |
| $2$ | $n\le1004$，$q\le97$ | 无 | $8$ |
| $3$ | $n\le4998$，$q\le10051$ | 无 | $10$ |
| $4$ | $n,q\le10^5$ | $\Sigma=\texttt{\{A,B\}}$ | $10$ |
| $5$ | $n,q\le3\times10^4$ | $type=0$ | $10$ |
| $6$ | $n,q\le10^5$ | $l=1,r=n$ | $10$ |
| $7$ | $n\le5014$ | 无 | $10$ |
| $8$ | $n,q\le10^5$ | 无 | $40$ |
对于 $100\%$ 的数据，$1\le n,q\le10^5$，$1\le l\le r\le n$，$type\in\{0,1\}$，$s$ 仅由大写字母构成。
若非特殊说明，本题 $type=1$ 且 $9\times10^4\le n,q\le10^5$。