Word Count

Program time limit: 2 seconds

Program memory limit: 512 MB

Joceline has a grid of size $N \cdot M$ filled with letters of the alphabet. Each row except for the first can be left-shifted by some value $X$ - that is, replace the $i^{\text{th}}$ value with the $(i + X) \% M^{\text{th}}$ value.

You are given a dictionary of $D$ words, each $N$ long. The wordcount of the grid is the number of columns with valid words.

You are given $Q$ queries of the form:

You are given values $i$ and $j$, you then shift the $i^{\text{th}}$ row by $j$
Joceline shifts every other row except for the first by a random value
Output the expected wordcount after these shifts

The grid is reset after each query.

Input

The first line contains two integers $N$ and $M$, representing the dimensions of the grid.
The next $N$ lines each contain a string of length $M$ consisting of lowercase characters, representing the grid.
The next line contains an integer $D$, representing the number of words in the dictionary.
The next $D$ lines each contain a string of length $N$ consisting of lowercase characters, representing the dictionary words.
The next line contains an integer $Q$, representing the number of queries.
The next $Q$ lines each contain two integers $i$ and $j$, representing the row to shift and the shift amount.

Constraints

For all test cases:

$1 \le N \le 50$
$1 \le M, D \le 10'000$
$1 \le Q \le 500'000$
$1 \le i \le N$
$0 \le j < M$
All strings contain only lowercase letters
All words in the dictionary are distinct

Scoring

For Subtask $1$ ($10\%$ of points): $1 \le M \le 500$
For Subtask $2$ ($10\%$ of points): $1 \le M \le 1000$
For Subtask $3$ ($10\%$ of points): $1 \le M \le 5000$
For Subtask $4$ ($70\%$ of points): There are no additional constraints

Output

For each query, output a single line containing the expected wordcount after the shifts as a fraction modulo $998244353$. Specifically, if the expected wordcount is $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers, output $(P \cdot Q^{-1}) \bmod 998244353$ where $Q^{-1}$ is the modular inverse of $Q$ modulo $998244353$.

Sample Input 1

3 4
abcd
baca
bcdb
6
abb
acb
adb
cbb
aab
bcb
2
2 1
3 2

Sample Output 1

1
499122177

Explanation 1

Query 1 (Row 2 is shifted left by 1)

Column 1:
Row 1, Col 1 = a.
After shifting Row 2 by 1, Row 2, Col 1 = a.
Required pattern is aa? -> the only dictionary word that fits is aab.
Row 3 is random; probability it is b: $2/4 = 1/2$.
Column 2:
Row 1, Col 2 = b.
After shifting Row 2 by 1, Row 2, Col 2 = c.
Required pattern is bc? -> the only dictionary word that fits is bcb.
Row 3 is random; probability it is b: $2/4 = 1/2$.
Column 3:
Row 1, Col 3 = c.
After shifting Row 2 by 1, Row 2, Col 3 = a.
Required pattern is ca? -> no dictionary word matches. Probability: $0$.
Column 4:
Row 1, Col 4 = d.
After shifting Row 2 by 1, Row 2, Col 4 = b.
Required pattern is db? -> no dictionary word matches. Probability: $0$.

Sum of probabilities: $1/2 + 1/2 + 0 + 0 = 1$. Answer: $1$.

Query 2 (Row 3 is shifted left by 2)

Column 1:
Row 1, Col 1 = a.
After shifting Row 3 by 2, Row 3, Col 1 = d.
Required pattern is a?d -> no dictionary word matches. Probability: $0$.
Column 2:
Row 1, Col 2 = b.
After shifting Row 3 by 2, Row 3, Col 2 = b.
Required pattern is b?b -> the only dictionary word that fits is bcb.
Row 2 is random; probability it is c: $1/4$.
Column 3:
Row 1, Col 3 = c.
After shifting Row 3 by 2, Row 3, Col 3 = b.
Required pattern is c?b → the only dictionary word that fits is cbb.
Row 2 is random; probability it is b: $1/4$.
Column 4:
Row 1, Col 4 = d.
After shifting Row 3 by 2, Row 3, Col 4 = c.
Required pattern is d?c -> no dictionary word matches. Probability: $0$.

Sum of probabilities: $1/4 + 1/4 + 0 + 0 = 1/2$. Answer: $499122177$.