题目描述

    alan写下了$N$个只由小写字母构成的字符串,由$1 \sim N$编号。

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

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

    你需要回答$Q$次询问,每一次询问将给出区间$[L,R]$,请你统计出在该区间内连续相似序列的个数。

    为了保证算法的在线性,记上一次询问的答案为$lastans$,则:

    $L=min((L \oplus lastans) ~ mod ~ N,(R \oplus lastans) ~ mod ~ N)+1$

    $R=max((L \oplus lastans) ~ mod ~ N,(R \oplus lastans) ~ mod ~ N)+1$

    其中$\oplus$表示按位异或,第一次询问时$lastans=0$

输入格式

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

    第二行$N$个字符串。

    接下来$Q$行,每行2个整数$L$$R$

输出格式

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

样例输入

5 2
acd bbd bcc ccb acd
0 3
2 7

样例输出

3
4

数据范围与约定

  • 对于20%的数据:$1 \leq N \leq 10,Q=1$
  • 对于60%的数据:$1 \leq N,Q \leq 1000$
  • 对于100%的数据:$1 \leq N,Q \leq 100000$,字符串的长度$ \leq 10$

样例解释

    第一次询问中,实际的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个序列为连续相似序列。