题目描述
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.
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 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$.
样例输入 Copy
1
4 4
aaba
a
aa
ab
cab
样例输出 Copy
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}$