Background

Translated from JOI Open 2016 T2 "RNA 鎖の販売 / Selling RNA Strands".

Problem Description

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.

Input Format

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 Format

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

2 3
AUGC
AGC
G C
AU C
A C

0
1
2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

2
1
1

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

1
0
1
2
3
2
0

Hint

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