文章拼接

【题目描述】

资料库里的文章都用只含 0、1 的字符串保存．管理员给定了一个非空字符串 $S$，想统计它在每篇文章中出现了多少次．一次出现对应一段连续的字符，不同出现可以重叠；例如，00 在 000 中出现了两次．

资料库最初只有文章 $T_0$，且 $|T_0|\ge |S|$．接下来依次生成 $n$ 篇文章．生成第 $i$ 篇文章时，先按给定顺序复制 $k_i$ 篇已有文章，再在末尾追加字符串 $D_i$：

$$T_i=T_{a_{i,1}}+T_{a_{i,2}}+\cdots+T_{a_{i,k_i}}+D_i$$

这里的 $+$ 表示首尾相接，不会增加分隔符．保证 $k_i\ge 1$、$0\le a_{i,j}<i$．同一篇文章可以被重复复制，$D_i$ 可以为空．复制不会改变已有文章．

请依次求出 $S$ 在 $T_1,T_2,\ldots,T_n$ 中的出现次数，对 $998244353$ 取模后输出．

【输入描述】

第一行输入整数 $n$．

第二行输入字符串 $S$．

第三行输入字符串 $T_0$．

接下来 $n$ 行，第 $i$ 行先输入整数 $k_i$，再输入 $k_i$ 个整数 $a_{i,1},\ldots,a_{i,k_i}$，然后输入整数 $d_i$，表示 $D_i$ 的长度．当 $d_i>0$ 时，这一行最后还有字符串 $D_i$；当 $d_i=0$ 时，这一行在整数 $0$ 后结束，不输入字符串．

【输出描述】

输出 $n$ 行，第 $i$ 行输出 $S$ 在 $T_i$ 中的出现次数对 $998244353$ 取模后的结果．

【样例 1】

输入

3
010
010
2 0 0 1 1
2 1 0 0
1 2 2 10

输出

2
4
5

解释

• $T_1=$ 0100101，两次出现的起始位置分别是 $1,4$．
• $T_2=$ 0100101010，四次出现的起始位置分别是 $1,4,6,8$．其中起始位置为 $6$ 的出现跨过了两篇文章的接缝．本次没有追加字符．
• $T_3=$ 010010101010，在原有四次出现之外，又增加了从位置 $10$ 开始的一次出现．

【样例 2】

输入

3
00
000
2 0 0 0
1 1 1 1
2 2 0 0

输出

5
5
7

解释

$T_1$ 是六个连续的 0，包含五次 00．$T_2$ 在末尾追加 1，出现次数不变．$T_3$ 在这个 1 后接上 000，又增加两次出现；接缝处没有新增出现．

【下发样例】

见选手目录下的 Data/sample3.in 至 Data/sample9.in 及对应的 .ans 文件．

样例	满足的条件
3	$\sum_{i=0}^{n}
4	$
5	$S,T_0,D_i$ 中的所有字符均为 0
6	所有 $k_i=1$
7	$
8	无特殊性质，规模适中
9	无特殊性质，达到完整规模

下载选手目录

【数据规模与约定】

对于所有数据，保证：

• $1\le n\le 2\times10^5$；
• $1\le |S|\le 2\times10^5$，$|S|\le |T_0|\le 3\times10^5$；
• $1\le k_i$，$\sum_{i=1}^{n}k_i\le 3\times10^5$；
• $0\le d_i$，$\sum_{i=1}^{n}d_i\le 3\times10^5$；
• $0\le a_{i,j}<i$；
• $S,T_0,D_i$ 只含 0、1．

文章展开后的长度不受上述输入规模的限制，可能远大于 $64$ 位整数的范围．

本题采用子任务计分，一个子任务的全部测试点通过后才能获得该子任务的分数．各子任务相互独立．

子任务编号	分数	附加限制
1	10	$\sum_{i=0}^{n} | T_i| \le 2\times 10^5$
2	8	$
3	12	$S,T_0,D_i$ 中的所有字符均为 0
4	20	所有 $k_i=1$
5		$
6	30	无