Background

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.

Problem Description

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.

Input Format

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 Format

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.

25 8 5 10
aaacdaabbbaabccaabcdaabcd

5
aaacd

Hint

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