P9922 [POI 2023/2024 R1] CzatBBB

Translated from [XXXI Olimpiada Informatyczna - Stage I](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [CzatBBB](https://sio2.mimuw.edu.pl/c/oi31-1/p/cza/)。

You are given a string $S$ of length $n$ and a parameter $k$. Let $R$ be the substring formed by the last $k$ letters of $S$. Suppose $S'$ is the new string obtained by appending one new letter to $S$. The appending rule is as follows. For each letter $X$, count how many times it appears in $S$ immediately after an occurrence of $R$. The letter with the highest frequency is chosen as the new appended letter. If multiple letters have the highest frequency, choose the smallest one. If $R$ does not occur anywhere else in $S$, then take $X = a$. Finally, we extend $S$ by appending the letter $X$ to its end. For example, let $S = \text{abaaabababa}$ and $k = 3$. Then the substrings where $R$ appears together with the following letter are: $\text{abaa}$, $\text{abab}$, $\text{abab}$. It most often appears with the letter $\text{b}$, so we append $\text{b}$ to $S$, obtaining $S' = \text{abaaabababab}$. Now $S' = \text{abaaabababab}$ and $R = \text{bab}$. The substrings where $R$ appears together with the following letter are: $\text{baba}$, $\text{baba}$. Therefore, we append $a$ to the end of $S'$. And so on. This operation will be performed infinitely many times. Your task is to write a program that outputs the characters from position $a$ to position $b$ of the extended string.

The first line contains four integers $n$, $k$, $a$, and $b$. The second line contains a string of length $n$, consisting of lowercase English letters, representing the word $S$.

Output the characters from the $a$-th to the $b$-th position of the string $S'$, i.e. the letters located at these positions in the extended word $S'$.

For all testdata, $2\leq n\leq10^6$, $1\leq k