题目背景

死而复生，生而复死。所谓的不死鸟就是这样的一种生物，在无尽的时间里无尽地循环往复。

果然最好还是别获得不老不死的能力吧。

题目描述

不死鸟的「一生」可以被看成一个长度不超过 $l_{\max}$ 的字符串 $S_0$。在无尽的轮回后形成了一个无限长的字符串 $S_{\mathrm{inf}}=S_0+S_0+S_0+\cdots$。现在截取 $S_{\infty}$ 前 $l$ 个字符，作为可观测时间里不死鸟的生命 $S_{\mathrm{fin}}$。

然而所谓的轮回并不是机械的循环往复。因此，$S_\mathrm{fin}$ 当中会有不超过 $n$ 个字符被修改成了别的字符，变成了 $S_{\mathrm{real}}$。

现在观测到了 $S_{\mathrm{real}}$，我们希望找到这轮回的最小片段 $S_0$。

当然，由于 $S_{\mathrm{real}}$ 从 $S_{\mathrm{fin}}$ 修改而来，可能不存在长度不超过 $l_{\max}$ 的字符串 $S_0$ 可以直接生成 $S_{\mathrm{real}}$。于是，现在只希望找到这样一个 $S_0'$，使得由它生成的 $S_\mathrm{fin}'$ 修改不超过 $m$ 个字符后可以变成 $S_{\mathrm{real}}$。

输入格式

第一行有四个正整数 $l,l_{\max},n,m$。

第二行描述观测到的长度为 $l$ 的字符串 $S_{\mathrm{real}}$。

输出格式

第一行输出一个正整数 $l_0$，表示你所找到的 $S_0$ 的长度。你应当保证 $1\le l_0\le l_{\max}$。

第二行输出一个长度为 $l_0$ 的字符串 $S_0$，表示你所找到的字符串。

25 8 5 10
aaacdaabbbaabccaabcdaabcd

5
aaacd

提示

样例解释

重要：样例仅供理解题意，不一定符合数据范围的约束。具体约束请参见「数据范围及约定」。

生成 $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$。