Colin has been 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.