Srwudi 是一个顶级生物科学家，他参与了很多基因工程工作。其中的一个工程需要研究某个物种基因片段的数目，也就是说，会有一个经过处理的样本DNA串 $S$，$S$ 的每一个子串都可能是一个基因。对于某个子串 $S[l..r]$，表示$S$中第 $l$ 个字符到第 $r$ 个字符组成的串，假如$S[l..r]$是一个回文串（一个串$T$为回文串，当且仅当将 $T$ 翻转后，仍与原串相同），那么 $S[l..r]$ 就是一个基因。注意，不同的基因可能重叠。比如说$aba$，就有4个基因，$S[1..1]=a,S[2..2]=b,S[3..3]=c,S[1..3]=aba$。但一个串$S$中可能含有很多功能相同的基因，对于两个基因 $T,P$，将他们视为两个字符串，他们只需要满足一下条件中的一个，那么就是不同的：

1. $T\text{的长度} \not= P\text{的长度}$
2. 存在一个位置$j$，满足$T[j] \not= P[j]$，其中$T[j],P[j]$表示分别在位置$j$上的字符。

比如对于 $aba$，就只有 $3$ 个功能不同的基因了。对于一个 DNA，Srwudi 想知道这个 DNA 串中会含有多少功能不同的基因。

但研究往往是困难重重的，由于技术有限，Srwudi提取样本串 $S$ 时不能保证十分精确，甚至有可能这个串$S$会是很多个DNA片段缠绕在一起的。因此，Srwudi首先将提取出来的东西展开成一条长度为 $N$ 的链，设为 $A$，注意 $A$ 依然是一个串，Srwudi接下来会进行 $Q$ 次猜测，每次他会选择一段 $A$ 中的子串 $A[l..r]$，并认为这就是一段合法的 DNA，然后算出 $A[l..r]$ 中有多少功能不同的基因，假如 $Q$ 足够大并且 Srwudi 的猜测足够准确的话，这个基因工程就能继续推进了。

然而，正当 Srwudi 准备开始工作时，他意识到一个困难，他无法快速地知道一个串 $S$ 中会有多少功能不同的基因，所以他找到了你，希望你能帮助他。 由于 Srwudi 的猜测不是盲目性的，他每次猜测后获得的数据会影响下一次的猜测，因此部分输入数据会进行一定的加密。

输入格式

第一行一个整数 $type$，若 $type=0$，表示这个数据没有进行加密，若 $type=1$，表示这个数据进行了加密。

第二行两个整数 $N,Q$，表示样本 $A$ 的长度为 $N$，以及Srwudi进行的猜测次数为 $Q$。 接下来 $Q$ 行，每行两个整数 $L',R'$。记 $lastans$ 为上一次猜测的答案，若这是第一次猜测，则 $lastans=0$，则这次猜测的$L,R$为，$L=L' \oplus (type \times lastans),R=R' \oplus (type \times lastans)$。

输出格式

输出 $Q$ 行，每行一个整数，表示对于这次猜测，$A[L..R]$ 中含有的功能不同的基因数目。

样例数据

样例输入

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

样例输出

7
2
5
3

样例解释

解密后的猜测依次为：

1 7
猜测的子串为abbabbb，不同功能的基因分别是：a,b,bb,bab,bbb,abba,bbabb
4 5
猜测的子串为ab，不同功能的基因分别是：a,b
4 8
猜测的子串为abbba，不同功能的基因分别是：a,b,bb,bbb,abbba
3 5
猜测的子串为bab，不同功能的基因分别是：a,b,bab

数据范围

对于所有数据，满足$Q \leq 2N$，且解密后的$L,R$，满足$1 \leq L \leq R \leq N$