#4932. 基因

内存限制:512 MiB 时间限制:80 Sec

题目描述

给定一个长度为n的字符串s,有q组询问,每个询问给定L,r,询问s[L..r]中有多少本质不同的回文子串。

输入格式

第一行一个整数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。字符串的字符集为小写字母

输出格式

输出共q行,代表每个询问的答案。

样例

样例输入


			
1
8 4
abbabbba
1 7
3 2
6 10
1 0

样例输出


			
7
2
5
2

数据范围与提示