P9196 [JOI Open 2016] Selling RNA Strands

**Translated from [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T2 "RNA 鎖の販売 / Selling RNA Strands".**

There are $N$ strings in a gene database. These strings consist only of `A`, `G`, `U`, `C` (it is guaranteed that every string contains only these four letters). There are $M$ queries. Each query contains two strings $P, Q$. You need to find: how many strings in the gene database have prefix $P$ and suffix $Q$ at the same time. For example, `GAC` has prefixes `G`, `GA`, `GAC`, and it has suffixes `C`, `AC`, `GAC`. So we can say: `GAC` has prefix `GA` and suffix `AC` at the same time.

The input has $N + M + 1$ lines. The first line contains two integers $N, M$. In the next $N$ lines, each line contains one string $S_i$, representing a string in the gene database. In the next $M$ lines, each line contains two strings separated by a space, representing one query.

Output $M$ lines. Each line contains one integer, the number of strings that satisfy the query conditions.

### Explanation for Sample 1 Query 1: cannot find any; Query 2: `AUGC` satisfies the conditions; Query 3: `AUGC` and `AGC` satisfy the conditions. ### Explanation for Sample 2 Note that strings in the gene database may be repeated. ### Constraints **This problem uses bundled testdata.** For all testdata, $1\le N, M \leq 10 ^ 5$, $1 \leq |S_i|, |P_j|, |Q_j| \le 10^5$, $1\le\sum |S_i|, \sum |P_j|, \sum |Q_j| \le 2\times 10^6$. - Subtask 1 (10 points): $N, M, |S_i|, |P_j|, |Q_j| \le 100$. - Subtask 2 (25 points): $N, M\le 5000$. - Subtask 3 (25 points): $\sum |S_i|, \sum|P_j|, \sum |Q_j| \le 10^5$. - Subtask 4 (40 points): no additional constraints. Translated by ChatGPT 5