Prefix Suffix Search

As an English learner, sometimes you cannot remember the entire spelling of an English word perfectly, and you can only remember its prefix and suffix. For example, you may want to use a word that begins with appr and ends with iate, but forget the middle part. It may be appreciate, appropriate, or something like them.

With an ordinary dictionary you can look up words beginning with a certain prefix, but filtering words that end with a certain suffix as well is inconvenient. So dictionary functionality that finds words having a given prefix and suffix is helpful. To start, let us count the number of such words instead of listing them all.

More formally, you are given a list of $N$ words. Then you are given $Q$ queries, each consisting of two strings. Write a program that outputs, for each query, the number of words in the given list that have both the given prefix and the given suffix.

The input consists of a single test case in the following format.

$N$ $Q$
$w_1$
...
$w_N$
$p_1$ $s_1$
...
$p_Q$ $s_Q$

The first line contains two integers $N$ and $Q$, where $N$ ($1 \le N \le 10^5$) is the number of words in the list and $Q$ ($1 \le Q \le 10^5$) is the number of queries. The $i$-th of the following $N$ lines contains a string $w\_i$. The $i$-th of the following $Q$ lines contains two strings $p\_i$ and $s\_i$, which are the prefix and suffix of the words to be searched for.

You can assume the following.

• All strings in the input are non-empty and consist only of lowercase English letters.
• The total length of the input strings does not exceed $2{,}500{,}000$.
• The words in the given list are unique: $w\_i \neq w\_j$ if $i \neq j$.
• The pairs of a prefix and a suffix are unique: $(p\_i, s\_i) \neq (p\_j, s\_j)$ if $i \neq j$.

For each query, output the number of words in the given list that have the given prefix and suffix, one per line.