A gene can be represented as a string consisting of four characters `A`, `U`, `G`, and `C`.
A gene bank contains $n$ genes. Given $q$ queries, each query consists of two strings $P$ and $Q$, and the task is to count how many strings in the gene bank have $P$ as a prefix and $Q$ as a suffix.
### Input
- The first line contains two integers $n$ and $q$.
- The next $n$ lines, each contains a string $S_i$, representing a gene in the gene bank.
- The next $q$ lines, each contains two strings $P_i$ and $Q_i$, representing a query.
### Output
- For each query, print an integer representing the number of strings that have $P_i$ as a prefix and $Q_i$ as a suffix.
### Constraints
- $1 \leq n, q, |S_i|, |P_i|, |Q_i| \leq 10^5$.
- $\sum |S_i|, \sum |P_i|, \sum |Q_i| \leq 2 \times 10^6$.
### Example
Input:
```
2 3
AUGC
AGC
G C
AU C
A C
```
Output:
```
0
1
2
```
### Subtasks
- Subtask 1 (10% of the points): $1 \leq n, q, |S_i|, |P_i|, |Q_i| \leq 100$.
- Subtask 2 (25% of the points): $n, q \leq 5000$.
- Subtask 3 (25% of the points): $\sum |S_i|, \sum |P_i|, \sum |Q_i| \leq 10^5$.
- Subtask 4 (40% of the points): No additional constraints.
