Description
给定一个长度为n的字符串s，有q组询问，每个询问给定L,r，询问s[L..r]中有多少本质不同的回文子串。
Input
第一行一个整数type，若type=0，表示这个数据没有进行加密，若
type=1，表示这个数据进行了加密。
第二行两个整数n,q。
第三行一个字符串s。
接下来q行，每行两个整数L′,r′。记Lastans为上一次询问的答案，
若这是第一次询问，Lastans=0，则这次猜测的L,r为，L=L′⊕(type×
Lastans),r=r′⊕(type×Lastans)。
N<=100000
q ≤ 2n, 且解密后的 L, r 满足 1 ≤ L ≤ r ≤ n。字符串的字符集为小写字母
Output
输出共q行，代表每个询问的答案。
Sample Input
18 4
abbabbba
1 7
3 2
6 10
1 0
Sample Output
72
5
2
