P9211 "Phoenix Possession"

To die and be reborn, to live and die again. A phoenix is such a creature, endlessly repeating this cycle through infinite time. So it is probably best not to gain eternal youth and immortality.

A phoenix’s “life” can be seen as a string $S_0$ of length at most $l_{\max}$. After endless cycles, it forms an infinite string $S_{\mathrm{inf}}=S_0+S_0+S_0+\cdots$. Now take the first $l$ characters of $S_{\mathrm{inf}}$ as the phoenix’s life within the observable time, denoted by $S_{\mathrm{fin}}$. However, the so-called cycle is not a rigid mechanical repetition. Therefore, in $S_\mathrm{fin}$, **no more than $n$ characters** are changed into other characters, becoming $S_{\mathrm{real}}$. Now we have observed $S_{\mathrm{real}}$, and we want to find the period $S_0$ of this cycle. But since the phoenix’s cycle is far too long, we only want to find a string $S_0'$ such that the $S_\mathrm{fin}'$ generated from it can be turned into $S_{\mathrm{real}}$ by modifying **no more than $m$ characters**.

The first line contains four positive integers $l,l_{\max},n,m$. The second line describes the observed string $S_{\mathrm{real}}$ of length $l$.

Output a positive integer $l_0$ on the first line, representing the length of the $S_0$ you found. You must guarantee $1\le l_0\le l_{\max}$. Output a string $S_0$ of length $l_0$ on the second line, representing the string you found.

### Sample Explanation The sample is only for understanding the statement, and **does not satisfy the Constraints**. For the actual constraints, see “Constraints and Conventions”. The $S_0$ used to generate $S_{\mathrm{real}}$ is $\verb!aabcd!$. - It generates $S_{\mathrm{inf}}=\verb!aabcdaabcdaabcdaabcdaabcd!\cdots$; - It generates $S_{\mathrm{fin}}=\verb!aabcdaabcdaabcdaabcdaabcd!$; - It generates $S_{\mathrm{real}\kern{-2.5pt}}=\verb!aaacdaabbbaabccaabcdaabcd!$. The sample output gives one possible $S_0'=\verb!aaacd!$. From this we compute the difference between $S_{\mathrm{fin}}'$ and $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}$$ The difference is $7$, not exceeding $m=10$, so it is acceptable. ### Constraints and Conventions For all testdata, it is guaranteed that $l=3\times 10^5$, $n=3\times 10^3$, $m=10^4$, and $1\le l_{\max} \le 10^5$. Translated by ChatGPT 5