草薙直哉拥有 $n$ 个由小写字母构成的非空模式串 $\{S_i\}$，同时他还有一个由小写字母构成的非空字符串 $Q$。

他认为两个字符串 $S,T$ 如果循环同构当且仅当 $|S|=|T|$，且存在 $i\in[0,|S|)$，满足当将 $S$ 循环右移 $i$ 位后，有 $S'=T$。

夏目蓝想考考草薙直哉，她总共有 $m$ 次询问，每次询问给出两个整数 $x,y$ （$x<y$）。想知道有多少个整数 $p$ 满足 $x\le p \le \text{min}(|Q|+x-y+1,y-1)$，在 $Q[x, p - 1]=Q[y,p-1-x+y]$ 的同时，有 $Q[p,y-1]$ 与某个模式串 $\{S_i\}$ 循环同构。

其中 $Q[l,r]$（$1\le l,r\le |Q|$）表示将 $Q$ 中字符下标从 $1$ 开始标号后，标号为中 $l$ 到 $r$ 的这一段子串。（包括左右端点）

输入格式

第一行输入两个正整数 $n,m$ ，表示模式串的个数以及询问的个数。

接下来 $n$ 行，每行读入一个由小写字母构成的非空字符串 $S_i$，表示草薙直哉的模式串集合。

接下来一行，读入一个由小写字母构成的非空字符串 $Q$。

接下来 $m$ 行，每行读入两个正整数 $x,y$ 表示询问的参数。具体的含义已经在题面描述中给出。

输出格式

总共输出 $m$ 行整数，其中第 $i$ 行输出第 $i$ 个询问的答案。

样例输入

5 5
baab
aa
aaab
ab
abaaa
bbaabababb
7 9
1 4
3 7
7 9
5 10

样例输出

1
0
1
1
0

另外两组样例见 sample/string/ 文件夹中：

string1.in/string1.out

string2.in/string2.out

数据范围

对于所有的数据我们有如下限制：

• $1\le n \le 5\times 10^5$ , $\sum |S_i|\le 5\times 10^5$
• $1\le |Q|\le 10^6$
• $1\le m \le 10^6$ , $1\le x < y\le |Q|$

特殊性质 A：所有 $S_i$ 串的长度均相等。