Finding Cyclic Isomorphism

题目描述

Colin is learning isomorphism theory recently and tries to apply it to string problems!

Define two strings $S, T$ to be cyclically isomorphic if and only if they satisfy all the following conditions:

• their lengths are equal, i.e., $|S|=|T|$;
• there exists an integer $i\in[0,|S|)$ such that if we cyclically right-shift $S$ for $i$ times, the resulting string $S'=T$.

For example, strings abcb and babc are cyclically isomorphic since we can cyclically right-shift the first string once to get the second string.

Now you are given $n$ non-empty pattern strings $S_1,S_2,\cdots,S_n$, and another non-empty text string $T$.

Colin raises $q$ questions; each question is described by an interval $[l_i, r_i]~(1\le l_i \lt r_i\le |T|)$. Colin wants to know how many integers $x$ satisfy all the following conditions:

• $x\in [l_i,\min(|T|+l_i-r_i+1,r_i-1)]$
• $T[l_i,x-1]=T[r_i,x+r_i-l_i-1]$
• $T[x,r_i-1]$ is cyclically isomorphic with at least one of $S_1,S_2,\cdots,S_n$.

Recall that $|T|$ represents the length of string $T$, and $T[a, b]~(1\le a\le b\le |T|)$ represents the substring of $T$ from the $a$-th character to the $b$-th character(including both boundaries). $T[a, b]~(a \gt b)$ represents an empty string, and empty strings are always equal.

输入格式

The first line contains two integers $n,q~(1\le n\le 5\times 10^5, 1\le q\le 10^6)$, representing the number of pattern strings and the number of questions.

For the following $n$ lines, each line contains a non-empty string $S_i$ consisting of lowercase letters, representing the $i$-th pattern string. It's guaranteed that $\sum_{i=1}^n |S_i|\le 5\times 10^5$.

The following line contains a non-empty string $T~(2\le |T|\le 10^6)$ consisting of lowercase letters.

For the following $q$ lines, each line contains two integers $l_i, r_i~(1\le l_i \lt r_i\le |T|)$, describing the $i$-th question.

输出格式

Output $q$ lines; the $i$-th line contains a single integer, representing the answer for the $i$-th question.

样例输入 #1

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

样例输出 #1

1
0
1
1
0