题目描述

题目译自 Open Olympiad in Informatics 2021 Day2 T2 「Вставить текст」。

阿里萨和安娅是文案工作者。最近她们接到一个订单：需要编写 $k$ 个关于相似主题的文本（字符串）。她们迅速开始工作，得到了 $k$ 个字符串 $S_1, \dotsc, S_k$，每个字符串的长度不超过 $m$，且由小写拉丁字母组成，其中 $S_1$ 的长度恰好为 $m$。

她们长期合作，有一个简单的方法来检查工作的原创性。原创性通过检查文本的子串来评估。阿里萨和安娅认为某个字符串是非原创的，如果它及其反转后的字符串在她们的文本中作为子串出现在相同的位置上。

为了加快检查速度，她们将字符串分割成块。分割成 $t$ 个块由序列 $a_0, a_1, \dotsc, a_t$ 定义，其中 $a_0 = 0$，$a_t = m$，且对于任意 $1 \leq i \leq t$，$a_{i-1} < a_i$。第 $i$ 个块定义为整数区间 $[a_{i-1}+1; a_i]$。块 $[a_{i-1}+1; a_i]$ 被称为有趣的，如果存在一个非原创字符串，恰好在该块定义的位置上出现在文本中。换句话说，块是有趣的，如果存在字符串 $S_l$ 和 $S_r$（可能 $l = r$），使得 $|S_l|, |S_r| \geq a_i$，且字符串 $S_{l, a_{i-1}+1}S_{l, a_{i-1}+2}\dotsc S_{l, a_i}$ 与字符串 $S_{r, a_i}S_{r, a_i-1}\dotsc S_{r, a_{i-1}+1}$ 相同，其中 $S_{t,j}$ 是字符串 $S_t$ 的第 $j$ 个字符。

例如，对于文本 $[\texttt{abba}, \texttt{ba}]$，序列 $(0,1,4)$ 和 $(0,1,2,3,4)$ 定义了有效的分割，而 $(1,2,3)$ 和 $(0,1,1,4)$ 则不是。对于分割 $(0,2,4)$，第一个块 $[1;2]$ 是有趣的，因为 $S_{1,1}S_{1,2}=S_{2,2}S_{2,1}=$ $\texttt{ab}$，而第二个块 $[3;4]$ 不是有趣的，因为对于唯一可能的对 $l = r = 1$，$S_{1,3}S_{1,4}=\texttt{ba}$ 和 $S_{1,4}S_{1,3}=\texttt{ab}$ 不相同。

分割被称为有趣的，如果其中的每个块都是有趣的。阿里萨和安娅希望找到将文本分割成最少块的有趣分割，以衡量工作的原创性。她们努力使这个问题符合现代标准并通过贝克德尔测试，现在请帮助她们编写一个程序来衡量原创性！

请注意，目标值是明确定义的，因为将字符串分割成 $m$ 个长度为 $1$ 的块总是能得到一个有趣的分割（每个块中可以选择 $l = r = 1$）。

输入格式

第一行包含三个整数 $t, k, m$ $(1 \leq k \leq 200000, 1 \leq m \leq 500000)$，分别表示子任务编号、文本总数和第一个文本的长度。

接下来的 $k$ 行中，第 $i$ 行输入 $S_i$，即第 $i$ 个文本，由小写拉丁字母组成。

保证 $|S_1|=m$，对于任意 $i>1$，$|S_i| \leq m$，且所有字符串的总长度不超过 $500000$。

输出格式

第一行输出一个整数 $t$，表示有趣分割中最少的块数。

第二行通过空格分隔输出 $t-1$ 个递增的整数 $a_1, \dotsc, a_{t-1}$，表示除最后一个块外的所有块的右边界编号（分割本身为 $[1;a_1], [a_1+1;a_2], \ldots ,[a_{t-1}+1;m]$）。

0 2 6
abcded
cba

2
3

在第一个样例中，第二个字符串 $\texttt{cba}$ 反转后与第一个字符串 $\texttt{abcded}$ 的前三个字符相同。而剩余的字符 $\texttt{ded}$ 形成回文，即该字符串与自身反转后相同。因此，我们可以将字符串分割成两个块 $[1;3]$ 和 $[4;6]$。显然，无法分割成更少的块，因为 $\texttt{abcded}$ 不是回文。

0 6 7
poggers
sus
amogus
tokyo
ghoul
sodluv

4
3 5 6

在第二个样例中，第一个块 $[1;3]$ 可以选择回文字符串 $\texttt{sus}$，第二个块选择第五个字符串的一部分 $\texttt{gho}\textbf{ul}$ 和第六个字符串的一部分 $\texttt{sod}\textbf{lu}\texttt{v}$，它们反转后彼此相同。第三个和第四个块则从任意字符串中选择单个字母。可以证明，无法分割成更少的块。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。