题目描述

    alan写下了个只由小写字母构成的字符串，由编号。

    对于两个字符串，如果它们的长度相同，且能够通过交换其中一个字符串中某些字符的位置，使其变成另一个字符串，则称这两个字符串相似。特别的，我们规定两个完全相同的字符串也相似。

    多个字符串可以组成一个序列，如果该序列中有且只有两个字符串相似，这称这个序列为相似序列。

    你需要回答次询问，每一次询问将给出区间，请你统计出在该区间内连续相似序列的个数。

    为了保证算法的在线性，记上一次询问的答案为，则：

    其中表示按位异或，第一次询问时。

输入格式

    第一行2个整数和，分别表示字符串的数目和询问的次数。

    第二行个字符串。

    接下来行，每行2个整数和。

输出格式

    对于每一次询问，输出一行，即该次询问区间内连续相似序列的个数。

样例输入

5 2
acd bbd bcc ccb acd
0 3
2 7

样例输出

3
4

数据范围与约定

• 对于20%的数据:。
• 对于60%的数据:。
• 对于100%的数据:，字符串的长度。

样例解释

    第一次询问中，实际的L=1,R=4，其中bcc ccb、bbd bcc ccb、acd bbd bcc ccb这3个序列为连续相似序列。

    第二次询问中，实际的L=2,R=5，其中bcc ccb、bbd bcc ccb、bcc ccb acd、bbd bcc ccb acd这4个序列为连续相似序列。