题目背景

原题链接：https://oier.team/problems/95。

题目描述

给定 $n$ 个字符串 $S_1, \ldots, S_n$ 以及一个字符串 $T$。

对于一个字符串 $R$，定义 $|R|$ 表示 $R$ 的长度、$R_{[l,r]}$ 表示 $R$ 的第 $l\sim r$ 个字符组成的字符串。字符串 $R'$ 是字符串 $R$ 的前缀当且仅当存在 $1\leq p\leq |R|$ 且 $p$ 为整数使得 $R'=R_{[1,p]}$。

定义一个字符串 $R$ 是好的当且仅当它是某个 $S_i$ 的前缀或 $R$ 为空。

对于若干字符串 $R_1,R_2,\dots,R_k$，定义 $R_1+R_2+\dots+R_k$ 为 $R_1,R_2,\dots,R_k$ 顺次拼接得到的字符串。

定义一个三元组 $(l,r,k)$（$l,r,k$ 均为整数）是好的当且仅当 $1\leq l\leq r\leq|T|$，$1\leq k\leq K$ 且存在 $k$ 个好的字符串 $R_1,R_2,\dots,R_k$ 使得 $R_1+R_2+\dots+R_k=T_{[l,r]}$。

请你求出好的三元组的数量，并对于每个 $i$ 求出有多少好的三元组 $(l,r,k)$ 满足 $l\leq i\leq r$。如果你只能求出两者中其一，也可以获得部分分数，见【输出格式】。

输入格式

第一行，三个非负整数 $id,n,K$，其中 $id$ 表示测试点编号（所有样例满足 $id=0$），$n$ 表示字符串数量，$K$ 表示对好的三元组的限制。

接下来 $n$ 行，每行一个字符串 $S_i$。

接下来一行，一个字符串 $T$。

输出格式

第一行，一个非负整数，表示好的三元组的数量。

第二行，$\lvert T\rvert$ 个非负整数，第 $i$ 个表示满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量。

本题使用自定义校验器进行评分，对于每个测试点：

• 如果你的程序正确地求出了好的三元组的数量并正确地对于每个 $1\leq i\leq |T|$ 求出了满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量，你可以获得该测试点 $100\%$ 的分数。
• 如果你的程序未能正确地求出了好的三元组的数量但正确地对于每个 $1\leq i\leq |T|$ 求出了满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量，你可以获得该测试点 $80\%$ 的分数。
• 如果你的程序正确地求出了好的三元组的数量但未能正确地对于每个 $1\leq i\leq |T|$ 求出了满足 $l\leq i\leq r$ 的好的三元组 $(l,r,k)$ 的数量，你可以获得该测试点 $60\%$ 的分数。
• 否则，你不能获得该测试点的任何分数。

注意，即使你希望获得某测试点 $80\%$ 或 $60\%$ 的分数，你也需要在第一行输出一个数并在第二行输出 $\lvert T\rvert$ 个数。

0 1 2
ab
abaab

13
5 3 5 6 3

0 3 2
abc
ac
b
bacabcab

27
4 9 6 11 10 5 6 5

0 10 10
wooogpgpoo
owpwgwwp
ooogpgpooo
gppwppgwoo
wooogpgpoo
wowooogpgp
gwwp
ggggogwgpp
wowooogpgp
pgpoooowpw
pgwgwggggggogwgppwppgwooggoogwowooogpgpoooowpwgwwp

7698
183 390 577 792 990 1213 1422 1651 1780 1889 1984 2099 2235 2355 2491 2458 2435 2426 2439 2466 2478 2498 2503 2489 2481 2477 2477 2483 2491 2527 2532 2559 2571 2540 2489 2433 2372 2276 2163 2041 1932 1803 1662 1491 1308 1111 900 702 486 252

提示

【样例解释 #1】

符合要求的 $(l,r,k)$ 有以下 $13$ 组：

• $(1,1,1)$；
• $(1,1,2)$；
• $(1,2,1)$；
• $(1,2,2)$；
• $(1,3,2)$；
• $(3,3,1)$；
• $(3,3,2)$；
• $(3,4,2)$；
• $(3,5,2)$；
• $(4,4,1)$；
• $(4,4,2)$；
• $(4,5,1)$；
• $(4,5,2)$。

【样例 #4】

见附件中的 string/string4.in 与 string/string4.ans。

该组样例满足测试点 $1\sim3$ 的约束条件。

【样例 #5】

见附件中的 string/string5.in 与 string/string5.ans。

该组样例满足测试点 $4\sim6$ 的约束条件。

【样例 #6】

见附件中的 string/string6.in 与 string/string6.ans。

该组样例满足测试点 $7\sim10$ 的约束条件。

【样例 #7】

见附件中的 string/string7.in 与 string/string7.ans。

该组样例满足测试点 $13\sim14$ 和测试点 $16\sim17$ 的约束条件。

【样例 #8】

见附件中的 string/string8.in 与 string/string8.ans。

该组样例满足测试点 $18\sim20$ 的约束条件。

【数据范围】

对于所有测试数据，保证：$1\leq n\leq10$，$1\leq |S_i|\leq5\times10^4$，$1\leq |T|,K\leq5\times10^5$，字符串仅包含小写英文字母 $\texttt{a}\sim\texttt{z}$。

测试点编号	$n\leq$	$\lvert S_i\rvert\leq$	$\lvert T\rvert\leq$	$K\leq$	特殊性质
$1\sim3$	$10$	$50$			无
$4\sim6$		$100$	$300$
$7\sim10$		$1000$	$5000$
$11\sim12$		$5\times10^4$	$5\times10^5$	$1$
$13\sim14$				$10$
$15$				$5\times10^5$	所有字符均为 $\texttt{a}$
$16\sim17$					所有字符在 $\{\texttt{a},\texttt{b}\}$ 中独立均匀随机生成
$18\sim20$					无