String

Alice and Bob are playing a string game.

Alice has a string $S$, Bob has a string $T$, in each round of the game, Bob will choose a string interval $T[l,r]$ in $T$ , Alice needs to find a string interval $S[l',r']$ in $S$ to make $T[l,r]$ is a substring of $S[l',r']$.

We define an interval of pairs $[l,r]$string $S$ if and only if $1\leq l\leq r\leq S_{len}$($S_{len}$ is the string $S$ length), all optional intervals of a string are all $l, r$ that satisfy the condition. $S[l,r]$ is a string formed by concatenating the $S$ string from the $l$th character to the $r$th character in order.

A string $T$ is a substring of the string $S$ if and only if the string $T$ can be obtained by removing some characters from the beginning and the end of the string $S$ (or not).

Both Alice and Bob find this game too boring, and they want to know if Bob randomly chooses one of all the intervals in the string $T$, how many intervals Alice can choose from the string $S$ and such that the string selected by Bob is a substring of the string selected by Alice.

The game will be played multiple times, and in each round, Bob will change the string $T$, so you will need to answer multiple sets of questions.

For the first line,input a positive integer $T(1\le T\le 5)$, representing the total number of test data.

For each test data,the first line contains two positive integers $n,q(1\leq n,q\leq 100000)$, which represent the length of the string and the number of queries.

The second line contains a string of length $n$ representing the $S$ string owned by Alice.

The next $q$ lines, each line contains a string, representing the query string $T$.

It is guarantees that the length of all query strings does not exceed $10^6$ in one test.

It is guaranteed that the input string contains only English lowercase letters.

For each query, output a line with a positive integer representing the expected number, and the answer modulo $998244353$.

1
4 4
aaba
a
aa
ab
cab

9
7
332748124
166374062

For the third query, $Bob$ can choose from three intervals of $[1,1][2,2][1,2]$, and the corresponding $Alice$ has $9,6,4$ intervals to choose from, So the answer is $\frac{9+6+4}{3}$

2023“钉耙编程”中国大学生算法设计超级联赛（6）