「不死鸟附体」

不死鸟的「一生」可以被看成一个长度不超过 $l_{\max}$ 的字符串 $S_0$。在无尽的轮回后形成了一个无限长的字符串 $S_{\mathrm{inf}}=S_0+S_0+S_0+\cdots$。现在截取 $S_{\mathrm{inf}}$ 前 $l$ 个字符，作为可观测时间里不死鸟的生命 $S_{\mathrm{fin}}$。 然而所谓的轮回并不是机械死板的循环往复。因此，$S_\mathrm{fin}$ 当中会有**不超过 $n$ 个字符**被修改成了别的字符，变成了 $S_{\mathrm{real}}$。 现在观测到了 $S_{\mathrm{real}}$，我们希望找到这轮回的周期 $S_0$。然而由于不死鸟的轮回太过漫长，我们只希望找到这样一个 $S_0'$，使得由它生成的 $S_\mathrm{fin}'$ 修改**不超过 $m$ 个字符**后就可以变成 $S_{\mathrm{real}}$。 ## Input 第一行有四个正整数 $l,l_{\max},n,m$。 第二行描述观测到的长度为 $l$ 的字符串 $S_{\mathrm{real}}$。 ## Output 第一行输出一个正整数 $l_0$，表示你所找到的 $S_0$ 的长度。你应当保证 $1\le l_0\le l_{\max}$。 第二行输出一个长度为 $l_0$ 的字符串 $S_0$，表示你所找到的字符串。 [samples] ## Background 死而复生，生而复死。所谓的不死鸟就是这样的一种生物，在无尽的时间里无尽地循环往复。 果然最好还是别获得不老不死的能力吧。 ## Note ### 样例解释 样例仅供理解题意，**不符合数据范围的约束**。具体约束请参见「数据范围及约定」。 生成 $S_{\mathrm{real}}$ 所用的 $S_0=\verb!aabcd!$。 - 由此生成 $S_{\mathrm{inf}}=\verb!aabcdaabcdaabcdaabcdaabcd!\cdots$； - 由此生成 $S_{\mathrm{fin}}=\verb!aabcdaabcdaabcdaabcdaabcd!$； - 由此生成 $S_{\mathrm{real}\kern{-2.5pt}}=\verb!aaacdaabbbaabccaabcdaabcd!$。 样例输出给出了一个可能的 $S_0'=\verb!aaacd!$。由此计算出 $S_{\mathrm{fin}}'$ 与 $S_{\mathrm{real}}$ 的差距： $$\begin{aligned} S_{\mathrm{fin}}'=&\texttt{aaacdaa\textcolor{red}a\textcolor{red}c\textcolor{red}daa\textcolor{red}ac\textcolor{red}daa\textcolor{red}acdaa\textcolor{red}acd}\cr S_{\mathrm{real}}=&\texttt{aaacdaabbbaabccaabcdaabcd}\cr \end{aligned}$$ 相差为 $7$，不超过 $m=10$，可以被接受。 ### 数据范围及约定 对于全部数据，保证 $l=3\times 10^5$，$n=3\times 10^3$，$m=10^4$，$1\le l_{\max} \le 10^5$。