问题描述

草薙直哉拥有 $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 \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

数据范围

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

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

| 测试点编号 | $\sum |S_i|\le$ | $m\le$ | $|Q|\le$ | 特殊性质 | | ---------: | --------------: | ------------: | ------------: | :--------: | | 1 | $300$ | $300$ | $300$ | 无 | | 2 | $300$ | $300$ | $300$ | 无 | | 3 | $10^5$ | $5000$ | $5000$ | 无 | | 4 | $10^5$ | $5000$ | $5000$ | 无 | | 5 | $5\times10^5$ | $5000$ | $5000$ | 无 | | 6 | $5\times10^5$ | $5000$ | $5000$ | 无 | | 7 | $5\times10^5$ | $5\times10^5$ | $10^6$ | 特殊性质 A | | 8 | $5\times10^5$ | $5\times10^5$ | $10^6$ | 特殊性质 A | | 9 | $10^5$ | $10^5$ | $5\times10^5$ | 无 | | 10 | $10^5$ | $10^5$ | $5\times10^5$ | 无 | | 11 | $2\times10^5$ | $2\times10^5$ | $10^6$ | 无 | | 12 | $2\times10^5$ | $2\times10^5$ | $10^6$ | 无 | | 13 | $2\times10^5$ | $5\times10^5$ | $10^6$ | 无 | | 14 | $2\times10^5$ | $5\times10^5$ | $10^6$ | 无 | | 15 | $3.5\times10^5$ | $5\times10^5$ | $10^6$ | 无 | | 16 | $3.5\times10^5$ | $5\times10^5$ | $10^6$ | 无 | | 17 | $5\times10^5$ | $8\times10^5$ | $10^6$ | 无 | | 18 | $5\times10^5$ | $8\times10^5$ | $10^6$ | 无 | | 19 | $5\times10^5$ | $10^6$ | $10^6$ | 无 | | 20 | $5\times10^5$ | $10^6$ | $10^6$ | 无 |

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