Problem Description

Translated from JOI Open 2016 T2 "Selling RNA Strands"

Due to the large number of test cases, only a portion of the test data is provided here. The remaining data can be tested here.

Problem Description

There are $N$ strings in the gene library, consisting only of the characters A, G, U, and C (each string contains all four letters).

There are $M$ queries, each containing two strings $P$ and $Q$. Determine how many strings in the gene library have both the prefix $P$ and the suffix $Q$.

For example, GAC has prefixes G, GA, GAC and suffixes C, AC, GAC. Thus, we can say that GAC has both the prefix GA and the suffix AC.

Input Format

The input consists of $N + M + 1$ lines.

The first line contains two integers $N$ and $M$.
The next $N$ lines each contain a string $S_i$, representing a string in the gene library.
The next $M$ lines each contain two space-separated strings, representing a query.

Output Format

The output consists of $M$ lines, each containing a single integer representing the number of strings that meet the query conditions.

Sample Input and Output

Sample Input #1

2 3
AUGC
AGC
G C
AU C
A C

Sample Output #1

0
1
2

Sample Input #2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

Sample Output #2

2
1
1

Sample Input #3

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

Sample Output #3

1
0
1
2
3
2
0

Notes

Sample 1 Explanation

First query: No string found.
Second query: AUGC meets the condition.
Third query: Both AUGC and AGC meet the condition.

Sample 2 Explanation

Note that strings in the gene library can be repeated.

Data Constraints

This problem is tested in bundles.

For all data, $1 \leq N, M \leq 10^5$, $1 \leq |S_i|, |P_j|, |Q_j| \leq 10^5$, $1 \leq \sum |S_i|, \sum |P_j|, \sum |Q_j| \leq 2 \times 10^6$.

• Subtask 1 (10 points): $N, M, |S_i|, |P_j|, |Q_j| \leq 100$.
• Subtask 2 (25 points): $N, M \leq 5000$.
• Subtask 3 (25 points): $\sum |S_i|, \sum |P_j|, \sum |Q_j| \leq 10^5$.
• Subtask 4 (40 points): No additional constraints.

见题面 Input 部分

见题面 Output 部分