Phoenix Rebirth

The legend tells that the immortal phoenix's life can be represented as a string \(S_0\) whose length does not exceed \(\ell_{\max}\). After infinite cycles, an infinite string is formed as

\(S_{\mathrm{inf}} = S_0 + S_0 + S_0 + \cdots\),

and if we take the first \(l\) characters, we obtain \(S_{\mathrm{fin}}\), which represents the observable life of the phoenix.

However, the cycle is not mechanically perfect; up to \(n\) characters in \(S_{\mathrm{fin}}\) might have been altered, resulting in the observed string \(S_{\mathrm{real}}\). Your task is to find a candidate cycle string \(S'_0\) (of length at most \(\ell_{\max}\)) such that when you form \(S'_{\mathrm{fin}}\) (by repeating \(S'_0\) until its length is \(l\)), you can transform \(S'_{\mathrm{fin}}\) into \(S_{\mathrm{real}}\) with at most \(m\) modifications.

If there are multiple valid candidates, output any one. If no valid candidate exists, output -1.

inputFormat

The first line contains four integers: \(\ell_{\max}\), \(l\), \(n\), \(m\) (where \(\ell_{\max}\) is the maximum allowed length of the cycle string, \(l\) is the length of the observed life string, \(n\) is the maximum number of modifications that originally occurred, and \(m\) is the maximum number of modifications allowed for your candidate).

The second line contains the string \(S_{\mathrm{real}}\) of length \(l\), consisting of lowercase English letters.

outputFormat

If a valid candidate cycle string \(S'_0\) exists such that by repeating it to form a string \(S'_{\mathrm{fin}}\) (of length \(l\)) the Hamming distance between \(S'_{\mathrm{fin}}\) and \(S_{\mathrm{real}}\) is at most \(m\), output \(S'_0\). Otherwise, output -1.

sample

3 6 2 1
ababaa

ab